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

using ll = long long;
using vint = vector<int>;
using vvint = vector<vint>;
using pint = pair<int, int>;
using vpint = vector<pint>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
#define repi(n) for (int i = 0; i < n; i++)
#define repj(n) for (int j = 0; j < n; j++)
#define repk(n) for (int k = 0; j < n; k++)
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, a, b) for (int i = a; i < b; i++)
#define repv(itr) for (auto&& v : itr)
#define swap(x, y)    \
  {                   \
    auto ___temp = x; \
    x = y;            \
    y = ___temp;      \
  }

const int dx[] = {-1, 0, 0, 1, -1, -1, 1, 1};
const int dy[] = {0, -1, 1, 0, -1, 1, -1, 1};
template <typename T>
T minptr(T begin, T end) {
  T re = begin;
  for (T i = begin + 1; i != end; i++) {
    if (*i < *re) re = i;
  }
  return re;
}
template <typename T>
T maxptr(T begin, T end) {
  T re = begin;
  for (T i = begin + 1; i != end; i++) {
    if (*i > *re) re = i;
  }
  return re;
}
int __vmax(int x) {
  return INT_MAX;
}
double __vmax(double x) {
  return 1e+300;
}
ll __vmax(ll x) {
  return LLONG_MAX;
}
int __vmin(int x) {
  return INT_MIN;
}
double __vmin(double x) {
  return -1e+300;
}
ll __vmin(ll x) {
  return LLONG_MIN;
}
template <typename T>
vector<T> lis(T begin, T end, bool allowequal = false, bool lds = false) {
  using V = typename iterator_traits<T>::value_type;
  int n = end - begin;
  vector<V> a(n, lds ? __vmin(*begin) : __vmax(*begin));
  vector<int> id(n);
  if (lds && allowequal) {
    for (int i = 0; i < n; i++) {
      id[i] = n - 1 -
              (lower_bound(a.rbegin(), a.rend(), begin[i]) - 1 - a.rbegin());
      a[id[i]] = begin[i];
    }
  } else if (lds) {
    for (int i = 0; i < n; i++) {
      id[i] = n - 1 -
              (upper_bound(a.rbegin(), a.rend(), begin[i]) - 1 - a.rbegin());
      a[id[i]] = begin[i];
    }
  } else if (allowequal) {
    for (int i = 0; i < n; i++) {
      id[i] = upper_bound(a.begin(), a.end(), begin[i]) - a.begin();
      a[id[i]] = begin[i];
    }
  } else {
    for (int i = 0; i < n; i++) {
      id[i] = lower_bound(a.begin(), a.end(), begin[i]) - a.begin();
      a[id[i]] = begin[i];
    }
  }
  int m = *maxptr(id.begin(), id.end());
  vector<T> re(m + 1);
  for (int i = n - 1; i >= 0; i--) {
    if (id[i] == m) re[m--] = begin + i;
  }
  return re;
}
template <typename T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}

pair<ll, int> a[100000];
int main() {
  int n, m;
  cin >> n >> m;
  repi(n) {
    int x, y;
    cin >> x >> y;
    pair<ll, int> z(x, y);
    a[i] = z;
  }
  sort(a, a + n,
       [](pair<ll, int> a, pair<ll, int> b) { return a.first < b.first; });
  ll re = 0;
  repi(n) {
    int x = min(m, a[i].second);
    m -= x;
    re += a[i].first * x;
  }
  cout << re << endl;
}


Measured memory_bytes: 1792
h,w=map(int,input().split())
x=[]
for i in range(1,w):
    x1=[h*i,h*((w-i)//2),h*(w-i)-h*((w-i)//2)]
    x1.sort()
    x2=[h*i,(w-i)*(h//2),h*(w-i)-(w-i)*(h//2)]
    x2.sort()
    x.append(min(x1[-1]-x1[0],x2[-1]-x2[0]))
for i in range(1,h):
    x1=[w*i,w*((h-i)//2),w*(h-i)-w*((h-i)//2)]
    x1.sort()
    x2=[w*i,(h-i)*(w//2),w*(h-i)-(h-i)*(w//2)]
    x2.sort()
    x.append(min(x1[-1]-x1[0],x2[-1]-x2[0]))
print(min(x))


Measured memory_bytes: 10968
import bisect

A, B, Q = map(int, input().split())
K = []
T = []
for i in range(A):
    K.append(int(input()))
for j in range(B):
    T.append(int(input()))
K.sort()
T.sort()
l_1 = len(K)
l_2 = len(T)

Ans = []
for i in range(Q):
    c = int(input())
    p = bisect.bisect_right(K, c)
    if p >= l_1:
        p -= 1
    dis_1 = abs(c - K[p-1])
    dis_2 = abs(c - K[p])
    q_1 = bisect.bisect_right(T, K[p-1])
    q_2 = bisect.bisect_right(T, K[p])
    if q_1 >= l_2:
        q_1 -= 1
    if q_2 >= l_2:
        q_2 -= 1
    result_1 = min([dis_1 + abs(K[p-1] - T[q_1-1]), dis_1 + abs(K[p-1] - T[q_1]), dis_2 + abs(K[p] - T[q_2-1]), dis_2 + abs(K[p] - T[q_2])])

    p = bisect.bisect_right(T, c)
    if p >= l_2:
        p -= 1
    dis_1 = abs(c - T[p-1])
    dis_2 = abs(c - T[p])
    q_1 = bisect.bisect_right(K, T[p-1])
    q_2 = bisect.bisect_right(K, T[p])
    if q_1 >= l_1:
        q_1 -= 1
    if q_2 >= l_1:
        q_2 -= 1
    result_2 = min([dis_1 + abs(T[p-1] - K[q_1-1]), dis_1 + abs(T[p-1] - K[q_1]), dis_2 + abs(T[p] - K[q_2-1]), dis_2 + abs(T[p] - K[q_2])])
    Ans.append(min(result_1, result_2))

for i in Ans:
    print(i)

Measured memory_bytes: 98864
// Binary Search
import java.util.*;
import java.lang.*;

public class Main {
    
    static int n;
    static int[] s;
    
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        s = new int[n];
        for (int i = 0; i < n; i++) {
            s[i] = sc.nextInt();
        }
        int q = sc.nextInt();
        int count = 0;
        for (int i = 0; i < q; i++) {
            if (binarySearch(sc.nextInt())) {
                count++;
            }
        }
        System.out.println(count);
    }
    
    static boolean binarySearch(int target) {
        int right = n - 1;
        int left = 0;
        int pointer = (left + right) / 2;
        while (right >= left) {
            pointer = (left + right) / 2;
            if (target == s[pointer]) {
                return true;
            } else if (target < s[pointer]) {
                right = pointer - 1;
            } else {
                left = pointer + 1;
            }
        }
        return false;
    }
}


Measured memory_bytes: 67840
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;

int main()
{
    ll n;
    cin >> n;
    ll a[200002];
    ll rev[200002];
    for(int i = 0; i < n; i++){
        cin >> a[i];
        rev[a[i]] = i;
    }
    ll r[200002];
    priority_queue<int> quer;
    for(ll i = 0; i < n; i++){
        while(quer.size()){
            int lar = quer.top();
            if(lar > a[i]){
                quer.pop();
                r[rev[lar]] = i - 1;
            }
            else break;
        }
        quer.push(a[i]);
    }
    while(quer.size()){
        int lar = quer.top();
        quer.pop();
        r[rev[lar]] = n - 1;
    }
    ll l[200002];
    priority_queue<int> quel;
    for(ll i = n - 1; i >= 0; i--){
        while(quel.size()){
            int lar = quel.top();
            if(lar > a[i]){
                quel.pop();
                l[rev[lar]] = i + 1;
            }
            else break;
        }
        quel.push(a[i]);
    }
    while(quel.size()){
        int lar = quel.top();
        quel.pop();
        l[rev[lar]] = 0;
    }
    ll ans = 0;
    for(ll i = 0; i < n; i++) ans += a[i] * (i - l[i] + 1) * (r[i] - i + 1);
    cout << ans << endl;
}

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

int main(void){
	int a , b ;
	int d , r ;
	double f ;

	cin >> a >> b ;
	d = a / b ;
	r = a % b ;
	f = (double) a / b ;
	cout << d << " " << r << " " ;
	cout << fixed;
	cout.precision(5);
	cout << f << endl ;
	return 0;
}

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

#define ll long long int
#define All(a) (a).begin(),(a).end()

void solve(){
  int n,m;
 
  scanf("%d %d",&n,&m);
  char A[n][m];
  int ans[n][m]={};
  for(int i=0;i<n;i++){
    for (int  j = 0; j < m; j++)
    {
      cin >> A[i][j];
    }
  }

  for (int i = 0; i < n; i++){
    for (int  j = 0; j < m; j++){
      if(A[i][j]=='#'){
        if(i!=0) {
          ans[i-1][j]+=1;
        }
        if(j!=0){
          ans[i][j-1]+=1;
        }
        if(i!=n-1){
          ans[i+1][j]+=1;
        }
        if(j!=m-1){
          ans[i][j+1]+=1;
        }
        
        if(i!=0 && j!=0){
          ans[i-1][j-1]+=1;
        }
        if(i!=0 && j!=m-1){
          ans[i-1][j+1]+=1;
        }
        if(i!=n-1 && j!=0){
          ans[i+1][j-1]+=1;
        }
        if(i!=n-1 && j!=m-1){
          ans[i+1][j+1]+=1;
        }
      }
    }
  }


  for(int i=0;i<n;i++){
    for (int j = 0; j < m; j++)
    {
       if(A[i][j]=='#'){
         printf("#");
       }else{
        char c='0'+ans[i][j];
        printf("%c",c);
      }
     }
    printf("\n");
  }
}
int main(){
  /*
  int q;
  scanf("%d",&q);
  while(--q)solve();
  */
  solve();

  return 0;
}

Measured memory_bytes: 3724
#include <iostream>

using namespace std;

int main(){
  int N,K;
  cin >> N;
  cin >> K;
  int tmp = N / 2;
  int tmp2 = N % 2;
  tmp = tmp + tmp2;
  if(tmp - K >= 0){
cout<<"YES";
}else{
cout<<"NO";
}
return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a) (a).begin(),(a).end()
#define pb emplace_back
#define INF (1e9+1)

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


Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>

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

  std::vector<int> A(N), B(N);
  for (auto& ai: A) scanf("%d", &ai);
  for (auto& bi: B) scanf("%d", &bi);

  int res = 0;
  for (size_t i = 1; i <= N; ++i) {
    int a = std::accumulate(A.begin(), A.begin()+i, 0);
    int b = std::accumulate(B.begin()+(i-1), B.end(), 0);
    res = std::max(res, a+b);
  }
  printf("%d\n", res);
}


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

void dfs(int n,int m,vector<int>ans){
	if(n==0){
		for(int i=0;i<ans.size();i++){
			if(i!=0)cout<<' ';
			cout<<ans[i];
			}
			cout<<endl;
			return;
		}
		
	for(int i=m;i>0;i--){
		if(i>n)continue;
		ans.push_back(i);
		dfs(n-i,i,ans);
		ans.pop_back();
		}	
		return ;
	}

int main(){
	int n;
	while(cin>>n,n){
		vector<int>v;
		dfs(n,n,v);
		}
		return 0;
	}

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

#define for_(i,a,b) for(int i=(a);i<(b);++i)
typedef long long lint;
typedef pair< int, int > pii;

int N, M, dp[100010];
vector< vector< int > > adj;
vector< int > g[2], col;
map< int, int > part_cnt;

bool dfs(int v, int c) {
	if (col[v] != -1) {
		if (col[v] != c) return false;
		return true;
	}
	
	col[v] = c;
	g[c].push_back(v);
	
	for (int u : adj[v]) if (!dfs(u, 1 - c)) return false;
	
	return true;
}

lint calc(lint A) {
	memset(dp, -1, sizeof(dp));
	
	dp[0] = 0;
		
	for (auto it = part_cnt.begin(); it != part_cnt.end(); ++it) {
		int a = (*it).first, c = (*it).second;
		
		for_(j,0,N+1) {
			if (dp[j] >= 0) {
				dp[j] = c;
			} else if (j < a || dp[j - a] <= 0) {
				dp[j] = -1;
			} else {
				dp[j] = dp[j - a] - 1;
			}
		}
	}
	
	lint res = 0;
	
	for_(a,0,N+1) {
		if (dp[a] == -1) continue;
		lint B = N - (A + a);
		res = max(res, (A + a) * B);
	}
	
	return res;
}

void solve() {
	col.assign(N, -1);
	
	bool flag = true;
	lint A = 0;
	
	for_(v,0,N) {
		if (col[v] != -1) continue;
		for_(i,0,2) g[i].clear();
		
		flag &= dfs(v, 0);
		
		int a = min(g[0].size(), g[1].size()), b = max(g[0].size(), g[1].size());
		++part_cnt[b - a];
		A += a;
	}
		
	cout << (!flag ? -1 : calc(A) - M) << endl;
}

int main() {
	cin >> N >> M;
	
	adj.assign(N, vector< int >());
	
	for_(i,0,M) {
		int u, v;
		cin >> u >> v;
		--u; --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	
	solve();
}

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

struct team {
    int no;
    int point;
    int time;
    int penalty[11];
};

void swap(team *a, team *b) {
    team temp = *a;
    *a = *b;
    *b = temp;
}

int main() {
    int a, b, c = 1, d;
    int M, T, P, R;
    int m, t, p, j;
    int teamnum[2001] = {0};
    team answers[2001][51];
    
    while (cin >> M >> T >> P >> R) {
        if (M == 0 && T == 0 && P == 0 && R == 0)
            break;
        
        teamnum[c] = T;
        team teams[51];
        for (a = 1; a <= T; a++) {
            teams[a].no = a;
            teams[a].point = 0;
            teams[a].time = 0;
            for (b = 1; b <= P; b++) {
                teams[a].penalty[b] = 0;
            }
        }
        
        while (R--) {
            cin >> m >> t >> p >> j;
            if (j == 0) {
                teams[t].point += 1;
                teams[t].time += m;
                teams[t].time += teams[t].penalty[p];
            } else {
                teams[t].penalty[p] += 20;
            }
        }
        
        /* ??????????????? */
        for (a = 1; a < T; a++) {
            for (b = a+1; b <= T; b++) {
                if (teams[a].point < teams[b].point) {
                    swap(&teams[a], &teams[b]);
                } else if (teams[a].point == teams[b].point) {
                    if (teams[a].time > teams[b].time)
                        swap(&teams[a], &teams[b]);
                    else if (teams[a].time == teams[b].time && teams[a].no < teams[b].no)
                        swap(&teams[a], &teams[b]);
                }
            }
        }
        
        for (d = 1; d <= T; d++)
            answers[c][d] = teams[d];
        c++;
    }
    
    for (a = 1; a < c; a++) {
        b = 1;
        while (teamnum[a]--) {
            if (b != 1 && answers[a][b-1].point != answers[a][b].point) cout << ',';
            if (b != 1 && answers[a][b-1].point == answers[a][b].point) {
                if (answers[a][b-1].time < answers[a][b].time) cout << ',';
                else cout << '=';
            }
            //cout << " point:" << answers[a][b].point << " time:" << answers[a][b].time << ' ';
            cout << answers[a][b].no;
            b++;
        }
        cout << endl;
    }
    
    return 0;
}

Measured memory_bytes: 1260
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); ++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;}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin>>n;
    vector<int> h(n);
    rep(i, n) {
        cin>>h[i];
    }
    int tmp = 0;
    tmp = h[0]; 
    int ans = tmp;
    for(int i=1; i<n;i++){
        if(h[i]<=tmp){
            tmp = h[i];
        }else {
            ans += (h[i]-tmp);
            tmp = h[i];
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i ++)
#define irep(i,n) for (int i = (int)(n) - 1;i >= 0;--i)
using namespace std;
using ll = long long;
using PL = pair<ll,ll>;
using P = pair<int,int>;
constexpr int INF = 1000000000;
constexpr long long HINF = 1000000000000000;
constexpr long long MOD = 1000000007;// = 998244353;
constexpr double EPS = 1e-4;
constexpr double PI = 3.14159265358979;

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

    vector<int> A(3);
    rep(i,3) cin >> A[i];
    int k; cin >> k;
    sort(A.begin(),A.end());
    int ans = A[0] + A[1] + (A[2] << k);
    cout << ans << '\n';
    return 0;
}

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

int main() {
  int a, b, c, d;
  int l, r;
  string result;
  
  cin >> a >> b >> c >> d;
  l = a + b;
  r = c + d;
  
  if(r < l){
    result = "Left";
  }else if(l < r){
    result = "Right";
  }else{
    result = "Balanced";
  }
  
  cout << result << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
using namespace std;
int a[200010],b[200010];
int main()
{
	int n;scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	int l=1,r=n;
	for(int i=n;i>=1;i--)
		if((n-i)&1) b[r--]=a[i];
		else b[l++]=a[i];
	for(int i=1;i<=n;i++) printf("%d ",b[i]);printf("\n");
}

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

using namespace std;

#define maxn 1000007
#define ll long long int
#define db(x) cout<<#x<<" ->"<<x<<" "<<endl
#define db2(x,y) cout<<#x<<"->"<<x<<", "<<#y<<" -> "<<y<<endl
#define db3(x,y,z) cout<<#x<<" -> "<<x<<" , "<<#y<<" -> "<<y<<" , "<<#z<<" -> "<<z<<endl
#define prt(x) for(auto it = x.begin(); it!=x.end(); it++) { cout<<*it<<" "; } cout<<endl
#define IN freopen("input.txt","r",stdin)
vector< string > V = {"AMBIGUOUS","NA" ,"YYMM","MMYY"};
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
   // IN ;
    int n,k;
    cin>>n>>k;
    double P = 0.0;
    for(int i=1; i<=n; i++){
        double Pr =((double)1/(double)n) * 1.00;
  //      db(Pr);
        int s = i;
        int cnt = 0;
        while( s <=(k-1) ){
            s*=2;
            cnt++;
        }
        double r = pow(0.5,cnt);
        double temp =pow(0.5,cnt) * 1.00  * Pr;
  //      db3(i,cnt,temp);
        P+=temp;
    }
    cout<<fixed<<setprecision(12)<<P<<endl;

    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define LLINF 100000000000000000ll
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
template<class T> void chmin(T& a,const T& b){if(a>b)a=b;}
template<class T> void chmax(T& a,const T& b){if(a<b)a=b;}
int N,M;
vector<int> g[100100];
int a[100100];
bool used[100100];
priority_queue<int,vector<int>,greater<int> > p,q;
int K=0;
void dfs(int v){
	used[v]=true;
	p.push(a[v]);
	for(int i=0;i<g[v].size();i++){
		int u = g[v][i];
		if(!used[u])dfs(u);
	}
}
int main(){
	cin >> N >> M;
	for(int i=0;i<N;i++)cin >> a[i];
	for(int i=0;i<M;i++){
		int x,y;
		cin >> x >> y;
		g[x].pb(y);
		g[y].pb(x);
	}
	ll ans = 0;
	for(int i=0;i<N;i++){
		if(!used[i]){
			K++;
			dfs(i);
			ans += p.top();
			p.pop();
			while(!p.empty()){
				q.push(p.top());
				p.pop();
			}
		}
	}
	if(K==1){
		printf("0\n");
		return 0;
	}
	if(N-2*(K-1)<0){
		printf("Impossible\n");
		return 0;
	}
	for(int i=0;i<K-2;i++){
		ans += q.top();
		q.pop();
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 7420
#include <bits/stdc++.h>
 
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n)  for(int i=0;i<(n);++i)
#define REPr(i, n) for(int i=(n)-1;i>=0; --i)
#define FORq(i, m, n) for(int i = (m);i <= (n);++i)
#define FORqr(i, m, n) for(int i = (n);i >=(m);--i)
#define PB push_back
#define MP make_pair
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
#define SIN(x, S) (S.count(x) != 0)
#define M0(x) memset(x,0,sizeof(x))
#define FILL(x, y) memset(x,y,sizeof(x))
#define MM(x) memset(x,-1,sizeof(x))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef long long ll;
typedef long long integer;
///////////////////////////////////////////////
/* (๑╹◡╹) */
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll MOD = 1000000007;
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;
}
/* (๑╹◡╹)(๑╹◡╹)(๑╹◡╹)(๑╹◡╹)(๑╹◡╹)(๑╹◡╹) */
///////////////////////////////////////////////
const int MAX = 510000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
 



int main() {
//	COMinit();
	ll ans = 0;
	int a; cin >> a;
	string s; cin >> s;
	if(a<3200){s = "red";}
	

	cout << s << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;

typedef pair <int,int> pii;
typedef vector <pii> vpii;
typedef vector <int> vi;
typedef vector <vi> vvi;
typedef long long int lli;
typedef pair<lli,lli> plli;
typedef vector <plli> vplli;
typedef vector <lli> vlli;
typedef vector <vlli> vvlli;
typedef vector <string> vs;
typedef vector <bool> vb;

#define rep(i, n) for( i = 0; i < (n); ++i)
#define repA(i, a, n) for( i = a; i <= (n); ++i)
#define repD(i, a, n) for( i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sortr(x) sort(x.begin(),x.end(),greater <int> ())
#define mod 1000000007
#define ff first
#define ss second
#define fill(a,c)  memset(a, c, sizeof (a))
#define formap(i,v) for(auto &i: v)
#define dbg(x) cout << #x << " = " << x << '\n'
#define dbg2(x,y) cout<<#x<<" = "<<x<<" & "<<#y<<" = "<<y<<endl;
#define dbgstl(v) cout<<#v<<" = \n"; { int c=0; formap(it,v) \
cout<<"    "<<#v<<"["<< ++c <<"] = "<<it<<endl;} cerr<<endl
#define dbgstlp(v) cout<<#v<<" = \n"; { int c=0; formap(it,v) \
cout<<"    "<<#v<<"["<< ++c <<"] = "<<it.first<<" , "<<it.second<<endl;} cerr<<endl
#define PI  3.14159265358979323846
#define pb push_back



int main() {
    cin.sync_with_stdio(0);cin.tie(0);
    cin.exceptions(cin.failbit);
    
    int a,b,c,k;
    cin>>a>>b>>c>>k;
    while (b<=a){
         k--;
         b=b*2;
    }
    while (c<=b){
         k--;
         c=c*2;
    }
    if (k<0)cout<<"No";
    else cout<<"Yes";
    
    
    
    
    
    
    
    
    
    
     
   
   
	return 0;
}


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

int N;
int ball[10];
bool dfs(int,int,int);

int main(){
    cin>>N;
    while(N--){
        for(int i=0; i<10; i++)
            cin>>ball[i];
        if(dfs(0, 0, 0)) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}

bool dfs(int left, int right, int n){
    if(n==9 && (ball[9]>left || ball[9]>right)) return true;
    if(ball[n]>left && dfs(ball[n], right, n+1)) return true;
    if(ball[n]>right && dfs(left, ball[n], n+1)) return true;
    return false;
}


Measured memory_bytes: 3032
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
using namespace std;
#define rep(i,n) for(int i = 0;i<n;i++)
const long long MOD = 1000000007LL;
int main(){
    int n;
    cin >> n;
    long long a[n];
    int k = 0;
    long long ans = 0;
    rep(i,n){
        cin >> a[i];
        if(a[i]<0){
            a[i] = -a[i];
            k++;
        }
        ans+=a[i];
    }
    if(k%2 == 0){
        cout << ans << endl;
    }
    else{
        sort(a,a+n);
        cout << ans - 2*a[0] << endl;
    }
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main () {
	int n, m, k;
	cin >> n >> m >> k;
	int a[n];
	for (int i=0; i<n; i++) {
		cin >> a[i];
	}
	int b[m];
	for (int i=0; i<m; i++) {
		cin >> b[i];
	}
	vector<long long> sa(n+1);
	sa[0] = 0;
	for (int i=1; i<=n; i++) {
		sa[i] = sa[i-1]+a[i-1];
	}
	vector<long long> sb(m+1);
	sb[0] = 0;
	for (int i=1; i<=m; i++) {
		sb[i] = sb[i-1]+b[i-1];
	}
	int o = 0;
	for (int i=0; i<=n; i++) {
		if (k-sa[i] >= 0) o = max((long)o, i+(upper_bound(sb.begin(), sb.end(), k-sa[i])-sb.begin()-1));
	}
	cout << o << endl;
}

Measured memory_bytes: 8016
fun main(args: Array<String>) {
    val (x, y, a, b, c) = readLine()!!.split(" ").map { it.toInt() }
    val aList = readLine()!!.split(" ").map { it.toInt() }.sortedDescending()
    val bList = readLine()!!.split(" ").map { it.toInt() }.sortedDescending()
    val cList = readLine()!!.split(" ").map { it.toInt() }.sortedDescending()

    var result = 0L
    var i = 0
    var j = 0
    var k = 0
    while (i + j + k < x + y) {
        val n1 = if (i < a) aList[i] else -1
        val n2 = if (j < b) bList[j] else -1
        val n3 = if (k < c) cList[k] else -1

        if (n1 >= n2 && n1 >= n3 && i < x) {
            result += n1
            i++
        } else if (n2 >= n1 && n2 >= n3 && j < y) {
            result += n2
            j++
        } else if (n3 >= n1 && n3 >= n2) {
            result += n3
            k++
        } else if (j == y && i < x && n1 >= n3) {
            result += n1
            i++
        } else if (i == x && j < y && n2 >= n3) {
            result += n2
            j++
        } else {
            result += n3
            k++
        }
    }

    println(result)
}

Measured memory_bytes: 111604
#include<cstdio>
#include<queue>
#include<vector>
#include<map>

using namespace std;
typedef long long int lli;
typedef pair<lli,lli> P;

vector<P> G[500500]; // target, cost
lli dis[100500];

void dijkstra(lli r) {
    for(lli i=0; i<sizeof(dis)/sizeof(lli); i++)
        dis[i] = 0x7FFFFFFF;

    priority_queue<P, vector<P>, greater<P> > q;
    q.push(P(0,r));
    while(!q.empty()) {
        lli cost = q.top().first;
        lli now = q.top().second;
        q.pop();

        if(dis[now] <= cost)
            continue;
        dis[now] = cost;
        for(vector<P>::iterator it = G[now].begin(); it != G[now].end(); it++)
            q.push(P(cost+it->second,it->first));
    }
}

int main(void) {
    lli v,e,r;
    scanf("%lld%lld%lld",&v,&e,&r);
    for(lli i=0; i<e; i++) {
        lli s,t,d;
        scanf("%lld%lld%lld",&s,&t,&d);
        G[s].push_back(P(t,d));
    }
    dijkstra(r);
    for(lli i=0; i<v; i++)
        if(dis[i] == 0x7FFFFFFF)
            printf("INF\n");
        else
            printf("%lld\n", dis[i]);
    return 0;
}

Measured memory_bytes: 31104
n,t = map(int,input().split())
L = []
for i in range(n):
    a,b = map(int,input().split())
    L.append([a,b])
dp1 = [[0 for i in range(t)] for i in range(n+1)]
dp2 = [[0 for i in range(t)] for i in range(n+1)]
for i in range(n):
    a = L[i][0]
    b = L[i][1]
    for j in range(t):
        if j-a >= 0:
            dp1[i+1][j] = max(dp1[i][j], dp1[i][j-a]+b, dp1[i+1][j])
        else:
            dp1[i+1][j] = max(dp1[i][j],dp1[i+1][j])
for i in range(n):
    a = L[n-i-1][0]
    b = L[n-i-1][1]
    if i == 0:
        for j in range(a, t):
            dp2[n-i-1][j] = b
    else:
        for j in range(t):
            if j-a >= 0:
                dp2[n-i-1][j] = max(dp2[n-i][j], dp2[n-i][j-a]+b,dp2[n-i-1][j])
            else:
                dp2[n-i-1][j] = max(dp2[n-i-1][j], dp2[n-i][j])
ans = 0
for i in range(1,n+1):
    for j in range(t):
        ans = max(ans, dp1[i-1][j]+dp2[i][t-1-j]+L[i-1][1])
print(ans)


Measured memory_bytes: 196752
#include <stdio.h>
#include <string.h>

struct card{
	int num;
	char suit;
};

void bubbleSort(struct card *c, int n);
void selectionSort(struct card *c, int n);
int isStable(struct card *chg, char suitOrder[10][5], int len);
void showRes(struct card *chg, int len, int resStable);

int main(void)
{
	int n;
	scanf("%d", &n);
	int i;
	struct card a[n];
	char suits[10][5];
	memset(suits, '\0', 10 * 5 * sizeof(char));
	for(i = 0; i < n; i++){
		//scanf(" %[HCDS]", &a[i].suit);
		//scanf("%d", &a[i].num);
		scanf(" %[HCDS]%d", &a[i].suit, &a[i].num);
		//printf("%c ", a[i].suit);
		//printf("%d ", a[i].num);
		sprintf(suits[a[i].num], "%s%c", suits[a[i].num], a[i].suit);
		//printf("%s\n", suits[a[i].num]);
	}

	struct card a2[n], a3[n];
	memcpy(a2, a, sizeof(a));
	memcpy(a3, a, sizeof(a));

	//printf("kakikuke\n");
	bubbleSort(a2, n);
	int resStable = isStable(a2, suits, n);
	//printf("aiue\n");
	showRes(a2, n, resStable);
	
	selectionSort(a3, n);
	showRes(a3, n, isStable(a3, suits, n));

	return 0;
}

void bubbleSort(struct card *c, int n)
{
	//printf("bubble\n");
	int i, j;
	struct card buf;
	for(i = 0; i <= n - 1; i++){
		for(j = n - 1; j >= i + 1; j--){
			if(c[j].num < c[j - 1].num){
				buf = c[j];
				c[j] = c[j - 1];
				c[j - 1] = buf;
			}
		}
	}
	//printf("bubble_e\n");
}

void selectionSort(struct card *c, int n)
{
	int i, minj, j;
	struct card buf;
	for(i = 0; i <= n - 1; i++){
		minj = i;
		for(j = i; j <= n - 1; j++){
			if(c[j].num < c[minj].num){
				minj = j;
			}
		}
		if(i != minj){
			buf = c[i];
			c[i] = c[minj];
			c[minj] = buf;
		}
	}
}

int isStable(struct card *chg, char suitOrder[10][5], int len)
{
	char st[5] = "\0";
	int i;
	for(i = 0; i < len; i++){
		if((i > 0) && (chg[i].num != chg[i - 1].num)){
			memset(st, '\0', sizeof(st));
		}
		sprintf(st, "%s%c", st, chg[i].suit);
		if((i == len - 1) || ((i < len - 1) && (chg[i].num != chg[i + 1].num))){
			if(strcmp(st, suitOrder[chg[i].num]) != 0){
				return 0;
			}
		}
	}
	return 1;
}

void showRes(struct card *chg, int len, int resStable)
{
	int i;
	for(i = 0; i < len - 1; i++){
		printf("%c%d ", chg[i].suit, chg[i].num);
	}
	printf("%c%d\n", chg[len - 1].suit, chg[len - 1].num);
	if(resStable){
		printf("Stable\n");
	}else{
		printf("Not stable\n");
	}
}




Measured memory_bytes: 2084
#include <bits/stdc++.h>
//#include <boost/functional/hash.hpp>
//example: unordered_set< pair<int,int>,boost::hash< std::pair<int, int> > > used;
//priority_queue< pair<int,pair<int,int> >, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int> > > > pqueue;    //cost, vertex(行き先)
using namespace std;

#define MODULE 1000000007
#define MP make_pair
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second

template<class T,class U>inline void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>inline void chmax(T &t,U f){if(t<f)t=f;}
template<typename A, size_t N, typename T>
inline void Fill(A (&array)[N], const T &val){ //usage: int dp[10][10]; Fill(dp,INF);
    std::fill( (T*)array, (T*)(array+N), val );
}

typedef pair<int, int> P;
typedef long long LL;
const int INF = INT_MAX / 2;    //int_max->2*e+9 LLの時はLLONG_MAX
/*const int MAXN = 100001;

struct edge {
    edge(int to, int cost) : to(to), cost(cost) {}
    int to, cost;
};
vector<edge> graph[MAXN];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};*/

//-----Template---------
string s;
int main(){
    ios::sync_with_stdio(false); //cout<< fixed << setprecision(10);
    cin>>s;
    if(s[0]=='a' || s[0]=='e' || s[0]=='i' || s[0]=='o' || s[0]=='u'){
        cout<<"vowel"<<endl;
    }else{
        cout<<"consonant"<<endl;    
    }
    
}

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

#define mp make_pair

using namespace std;

typedef int32_t i32;
typedef uint32_t u32;
typedef int64_t i64;
typedef uint64_t u64;
typedef pair<int,int> pii;
typedef pair<i64,int> pli;
typedef pair<int,i64> pil;
typedef pair<i64,i64> pll;
typedef vector<int> vi;
typedef vector<i64> vl;

template <typename T>
T id(T b) {return b;};
template <class It>
bool all(It f,It l){return std::all_of(f,l,id<bool>);}
template <class It>
bool any(It f,It l){return std::any_of(f,l,id<bool>);}

const int MAX_N = 100;
int n;
double t[MAX_N+1];
double v[MAX_N+2];
//double b[MAX_N+1];
double b1[MAX_N+1];
double b2[MAX_N+1];

int main()
{
  cin >> n;
  t[0] = 0;
  for (int i = 1; i <= n; i++) {
    cin >> t[i];
    t[i] += t[i-1];
  }
  v[0] = v[n+1] = 0;
  for (int i = 1; i <= n; i++) cin >> v[i];
  for (int i = 0; i <= n; i++) {
    b1[i] = min(v[i],v[i+1]) + t[i];
    b2[i] = min(v[i],v[i+1]) - t[i];
  }
  for (int i = 0; i <= n; i++) {
    b1[i] = *min_element(b1+i,b1+n+1);
    b2[i] = *min_element(b2,b2+i+1);
  }

  double d = 0;
  for (int i = 1; i <= n; i++) {
    double vs = min(-t[i-1]+b1[i-1], t[i-1]+b2[i-1]);
    double ve = min(-t[i]+b1[i], t[i]+b2[i]);
    //printf("vs=%f v[%d]=%f ve=%f\n",vs,i,v[i],ve);
    double dt = t[i] - t[i-1];
    double p = (ve+dt-vs) / 2.0;
    if (v[i] <= vs + p) {
      double mdt = dt - (v[i] - vs) - (v[i] - ve);
      double v1 = (v[i]+vs)*(v[i]-vs)/2.0;
      double v2 = mdt*v[i];
      double v3 = (v[i]+ve)*(v[i]-ve)/2.0;
      //printf("v1=%f v2=%f v3=%f\n",v1,v2,v3);
      d += v1 + v2 + v3;
    } else {
      d += (2.0*vs+p)*p/2.0 + (2.0*ve+dt-p)*(dt-p)/2.0;
    }
    //printf("i=%d d=%f\n",i,d);
  }
  printf("%.10f\n", d);

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
#define ll long long
const int mod = 998244353, maxn = 1e5+10;
int N, M, K;
ll w[maxn], v[maxn], dp[maxn];

int main()
{
//    memset(dp, 0x3f,sizeof(dp));
    scanf("%d %d", &N, &M);
    for(int i = 1; i <= N; i++)
        scanf("%lld %lld", &w[i], &v[i]);
//    dp[0] = 0;
    for(int i = 1; i <= N; i++)
        for(int j = M; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
        }
    printf("%lld\n", dp[M]);
    return 0;
}


Measured memory_bytes: 4020
#include"bits/stdc++.h"
#include<boost/multi_array.hpp>
#include<boost/range/irange.hpp>
#include<boost/range/algorithm.hpp>
#include<boost/range/adaptors.hpp>

namespace adaptor = boost::adaptors;

void solve()
{
    int64_t N;
    std::cin >> N;
    std::vector<int64_t> d(N);
    for (auto& v : d) std::cin >> v;

    int64_t ans = 0;
    for (int64_t i = 0; i < N - 1; i++)
    {
        for (int64_t j = i + 1; j < N; j++)
        {
            ans += d[i] * d[j];
        }
    }

    std::cout << ans << std::endl;
}

int main()
{
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    solve();
}


Measured memory_bytes: 3656
#include <bits/stdc++.h>
#define rep(i,n) for (int i = (0); i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(x) (x).begin(),(x).end()
#define rrng(x) (x).rbegin(),(x).rend()
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define show(x) cout << #x << " = " << (x) << endl
#define show2(x,y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl
#define show3(x,y,z) cout << #x << " = " << (x) << ", " << #y << " = " << (y) <<  ", " << #z << " = " << (z) << endl
#define showv(v) rep(i,v.size()) printf("%d%c", v[i], i==v.size()-1?'\n':' ')
#define showv2(v) rep(j,v.size()) showv(v[j])
#define showt(t,n) rep(i,n) printf("%d%c", t[i], i==n-1?'\n':' ')
#define showt2(t,r,c) rep(j,r) showt(t[j],c)
#define showvp(p) rep(i,p.size()) printf("%d %d\n", p[i].first, p[i].second);
#define printv(v) rep(i,v.size()) printf("%d\n", v[i])
#define printt(t,n) rep(i,n) printf("%d\n", t[i])
#define incl(v,x) find(rng(v),x)!=v.end()
#define incls(s,c) s.find(c)!=string::npos
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define bit(n,k) ((n>>k)&1) // nのk bit目
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define uni(x) x.erase(unique(rng(x)),x.end())
#define SP << " " <<
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vs = vector<string>;
using P = pair<int, int>;
using T = tuple<int, int, int>;
using vp = vector<P>;
using vt = vector<T>;
const int mod = 1000000007;
const double EPS = 1e-9;
const int INF = (1<<30)-1;
const ll INFLL = (1LL<<62)-1;
#define dame { puts("No"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
inline int in() { int x; scanf("%d",&x); return x;}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
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; }

int n, a, b, c;
vi l(12);

int dfs(int cur, int as, int bs, int cs) {
  if (cur == n) {
    if (min({as,bs,cs}) == 0) return INF;
    return abs(as-a) + abs(bs-b) + abs(cs-c) - 30;
  }
  int ret0 = dfs(cur+1, as, bs, cs);
  int ret1 = dfs(cur+1, as+l[cur], bs, cs) + 10;
  int ret2 = dfs(cur+1, as, bs+l[cur], cs) + 10;
  int ret3 = dfs(cur+1, as, bs, cs+l[cur]) + 10;
  return min({ret0, ret1, ret2, ret3});
}

int main () {
  cin >> n >> a >> b >> c;
  rep(i,n) cin >> l[i];
  int ans = dfs(0,0,0,0);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#!python3

LI = lambda: list(map(int, input().split()))

# input
l = LI()


def main():
    d = {i: 0 for i in range(11)}
    for x in l:
        d[x] += 1
    if d[5] == 2 and d[7] == 1:
        ans = "YES"
    else:
        ans = "NO"
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int main(){
	long long i,j,k,m,n;
	long long a,b,c,d;
	long long x,y;
	while(scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&c,&d)!=EOF){
		int flag=0;
		for(i=0;i<=n-1;i++){
			x=a+c*i-(n-i-1)*d;
			y=a+d*i-(n-i-1)*c;
			if(b>=x && b<=y){
				flag=1;
				break;
			}
		}
		if(!flag)puts("NO");
		else puts("YES");
	}
	return 0;
}


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

typedef long long ll;
typedef pair<int, int> pii;

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

#define endl "\n"

void use_cio() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
}

template <class L, class R>
ostream &operator<<(ostream &os, pair<L, R> P) {
    return os << "(" << P.first << "," << P.second << ")";
}
template <class T>
ostream &operator<<(ostream &os, vector<T> V) {
    os << "[";
    for (auto x : V) os << x << ", ";
    return os << "]";
}
//--------------------------------------------------//
int n, m;
int x[100010];
int oldpar[100010];
struct Edg {
    int u, v, w, oru = -1, orv = -1;
    bool isbridge = 0;
    bool operator<(Edg b) const {
        return w < b.w;
    }
};
vector<Edg> edg;
struct UnionFind {
    vector<int> par, rank;
    vector<ll> sum;
    UnionFind(int n)
        : par(n), sum(n), rank(n, 0) {
        iota(all(par), 0);
        rep(i, n) sum[i] = x[i];
    }
    void join(int x, int y) {
        x = root(x);
        y = root(y);
        if (rank[x] < rank[y])
            par[x] = y, sum[y] += sum[x];
        else
            par[y] = x, sum[x] += sum[y];
        if (rank[x] == rank[y]) rank[x]++;
    }
    int root(int x) { return par[x] != x ? root(par[x]) : x; }
};
int main() {
    use_cio();
    cin >> n >> m;
    rep(i, n) cin >> x[i + 1];
    rep(i, m) {
        int u, v, w;
        cin >> u >> v >> w;
        edg.push_back({u, v, w});
    }
    sort(all(edg));
    UnionFind uf(n + 1);
    for (auto &e : edg) {
        if (uf.root(e.u) != uf.root(e.v)) {
            e.oru = uf.root(e.u);
            e.orv = uf.root(e.v);
            e.isbridge = 1;
            uf.join(e.u, e.v);
        }
    }

    sort(edg.rbegin(), edg.rend());
    int ans = 0;
    for (auto e : edg) {
        if (uf.sum[uf.root(e.u)] >= e.w) continue;
        ans++;
        if (e.isbridge) {
            int ru = e.oru, rv = e.orv;
            if (uf.rank[ru] < uf.rank[rv]) {
                uf.par[ru] = ru;
                uf.sum[rv] -= uf.sum[ru];
            } else {
                uf.par[rv] = rv;
                uf.sum[ru] -= uf.sum[rv];
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 5364
class Node
  attr_accessor :parent, :rank

  def initialize(n)
    @parent = n
    @rank = 0
  end
end

class UnionFindTree
  def initialize(n)
    @nodes = (0..n).to_a.map { |i| Node.new(i) }
  end

  def find(x)
    return x if @nodes[x].parent == x

    return @nodes[x].parent = find(@nodes[x].parent)
  end

  def unite(a, b)
    a = find(a)
    b = find(b)
    return if a == b

    if @nodes[a].rank < @nodes[b].rank
      @nodes[a].parent = b
    else
      @nodes[b].parent = a
      @nodes[a].rank += 1 if @nodes[a].rank == @nodes[b].rank
    end
  end

  def same?(a, b)
    find(a) == find(b)
  end

  def parents
    @nodes.map(&:parent)
  end
end

N, M = gets.split.map(&:to_i)

ans = 0

data = []
M.times do
  data << gets.split.map(&:to_i)
end

M.times do |i|
  a, b = data[i]
  uf = UnionFindTree.new(N)

  M.times do |j|
    next if j == i
    c, d = data[j]
    uf.unite(c - 1, d - 1)
  end
  ans += 1 unless uf.same?(a - 1, b - 1)
end

puts ans

Measured memory_bytes: 1788
#include <iostream>
using namespace std;
int main() {
  string N; cin>>N;
  int sum=0;
  for (int i=0; i<N.size(); i++) {
    sum += (N[i]-0x30);
  }
  if (sum % 9 == 0)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3732
#include<bits/stdc++.h>
#define N 105
#define show(x) cerr << #x << " = " << x << '\n'
using namespace std;
int dx[2] = {0,1};
int dy[2] = {1,0};

char s[105][105];
int h, w, sum;

bool check(int x,int y){
    return x > 0 && x <= h && y > 0 && y <= w;
}
int dps(){
    int dp[N][N];
    for(int i = 0;i < N;i ++)dp[i][0] = dp[0][i] = 0x3f3f3f3f;
    dp[0][1] = dp[1][0] = 0;
    for(int i = 1;i <= h;i ++){
        for(int j = 1;j <= w;j ++){
            if(s[i][j] == '#'){
                dp[i][j] = min(dp[i - 1][j] + (s[i][j] != s[i - 1][j]),dp[i][j - 1] + (s[i][j] != s[i][j - 1]));
            }
            else{
                dp[i][j] = min(dp[i][j - 1],dp[i - 1][j]);
            }
        }
    }
    return dp[h][w];
}
int main(int argc,char *argv[]){
    cin >> h >> w;
    for(int i = 1;i <= h;i ++){
        scanf("%s",s[i] + 1);
    }
    cout << dps();
}

Measured memory_bytes: 256
package main

import (
  "fmt"
)

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

  ans := make([]int,m)
  for i:=0;i<n;i++ {
    fmt.Scan(&k)
    for j:=0;j<k;j++ {
      fmt.Scan(&tmp)
      ans[(tmp-1)]++
    }
  }
  count:=0
  for i:=0;i<m;i++ {
    if ans[i] == n {
      count++
    }
  }
  fmt.Println(count)
}


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



int main() {
  string S; cin >> S;
  string T = "ACGT";
  int m = S.size();
  int s[m];
  int ans = 0;
  int cnt = 0;

  rep(i,m) s[i] = 0;

  rep(i,m){
    rep(j,4){
      if(S[i] == T[j]) s[i] = 1;
    }
  }


  rep(i,m){
    if(s[i] == 1) {
      cnt++;
    }
    else {
      ans = max(ans,cnt);
      cnt = 0;
    }
  }
  ans = max(ans,cnt);
  cout << ans << endl;


  return 0;
}








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

using namespace std;

const int INF = 1e9;
const int N = 1e5;
const int MOD = 1e9 + 7;
const double EPS = 1e-6;

const double PI = acos(-1);


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int a, b;
    cin >> a >> b;
    int res = INF;
    for (int ans = 1; ans <= N; ans++) {
        if (ans * 8 / 100 == a && ans / 10 == b)
            res = min(res, ans);
    }
    if (res == INF)
        res = -1;
    cout << res;
}

Measured memory_bytes: 256
/*
	Carry a Cheese
*/
#include	<iostream>
#include	<cmath>

using namespace std;

int main(void) {
	while(1){
		int lx, ly, lz, n;
		double dxy, dyz, dzx;
		
		cin >> lx >> ly >> lz;
		
		if(lx == 0 && ly == 0 && lz == 0) { break; }
		
		dxy = sqrt(lx * lx + ly * ly);
		dyz = sqrt(ly * ly + lz * lz);
		dzx = sqrt(lz * lz + lx * lx);
		
		cin >> n;
		
		for(int i = 0; i < n; i++) {
			int r;
			
			cin >> r;
			r *= 2;
			if(r > dxy || r > dyz || r > dzx) {
				cout << "OK" << endl;
			} else {
				cout << "NA" << endl;
			}
		}
	}
	
	return 0;
}

Measured memory_bytes: 1156
#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#define ll long long
#define maxn 200005
#define re register
#define inf 1e9
#define eps 1e-10
using namespace std;

inline int read()
{
	int 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;
}

int n;
char s1[maxn],s2[maxn];

int main()
{
	cin>>n; cin>>s1>>s2;
	for(int i=0;i<n;i++) printf("%c%c",s1[i],s2[i]);
	return 0;
}

Measured memory_bytes: 256
num = gets.chomp.to_i
k = gets.chomp.to_i
val=gets.chomp.split.map(&:to_i)
ans = 0
num.times do |i|
    if val[i]*2<(k-val[i])*2 then
        ans=ans+val[i]*2
    else
        ans=ans+(k-val[i])*2
    end
end
puts ans


Measured memory_bytes: 1788
import java.util.Scanner;

public class Main{
  public static void main(String[] args){
    Scanner scanner = new Scanner(System.in);
    int y = 700;
    char[] c = scanner.nextLine().toCharArray();
    
    for(int i = 0; i < c.length; i++){
      if(c[i] == 'o'){
        y = y + 100;
      }
    }
    
    System.out.println(y);
    scanner.close();
  }
}

Measured memory_bytes: 21844
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;
import java.math.BigInteger;

public class Main implements Runnable {
	
	//static int mod = 1000000007;
	
    public static void main(String[] args) {
    	new Thread(null, new Main(), "", 1024 * 1024 * 1024).start();
    }
    
    public void run() {
        PrintWriter out = new PrintWriter(System.out);
        FastScanner sc = new FastScanner();
        
        int a = sc.nextInt();
        int b = sc.nextInt();
        
        int c = a+b;
        
        if(c%2 == 0){
        	out.println(c/2);
        }
        else{
        	out.println("IMPOSSIBLE");
        }
        
        out.flush();
    }

}

class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;
	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}
	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}
	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}
	public boolean hasNext() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++;
		return hasNextByte();
	}
	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	public long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}
	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
			throw new NumberFormatException();
		return (int) nl;
	}
	public int[] nextintArray(int n){
		int[] a = new int[n];
		for(int i=0;i<n;i++){
			a[i] = nextInt();
		}
		return a;
	}
	public long[] nextlongArray(int n){
		long[] a = new long[n];
		for(int i=0;i<n;i++){
			a[i] = nextLong();
		}
		return a;
	}
	public Integer[] nextIntegerArray(int n){
		Integer[] a = new Integer[n];
		for(int i=0;i<n;i++){
			a[i] = nextInt();
		}
		return a;
	}
	public int[][] nextintMatrix(int h, int w){
		int[][] mat = new int[h][w];
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				mat[i][j] = nextInt();
			}
		}
		return mat;
	}
	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

Measured memory_bytes: 24660
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
double v[101];
double solve(int i) {
	if (i != 0)return (double)((v[i] + solve(--i)) / 2.0);
	else return v[i];
}

int main() {
	int n;
	int a;
	double ans;

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	sort(v, v + n);

	ans = solve(n-1);

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


Measured memory_bytes: 256