akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <tuple>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <random>
#include <set>
#include <stack>

//#include <bits/stdc++.h>
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i,i0,n) for(int (i)=(i0);(i)<(n);(i)++)
#define FORR(i,i0,n) for(int (i)=(n)-1; (i)>=(i0);(i)--)
#define SORT(x) sort(x.begin(),x.end())
#define SORTR(x) sort(x.begin(),x.end(),greater<int>())
#define rn return
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#include <time.h>
typedef std::pair<int,int> P;
using namespace std;
using ll = long long;




int main(){
    int n;
    cin >> n;
    map<int,int> boss;
    FOR(i,1,n){
        int b;
        cin >> b;
        boss[b]++;
    }
    FOR(i,1,n+1){
        cout << boss[i] << endl;
    }
    
}









Measured memory_bytes: 13004
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define mk make_pair
#define all(a) a.begin(), a.end()
#define len(a) (int)a.size()

using namespace std;

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

void solve(){
	int x, n;
	cin >> x >> n;
	set <int> s;
	for(int i = 0; i < n; i++){
		int tmp;
		cin >> tmp;
		s.insert(tmp);
	}
	
	int l = x, r = x;
	while(1){
		if(!s.count(l)){
			cout << l << endl;
			return;
		}
		l--;
		if(!s.count(r)){
			cout << r << endl;
			return;
		}
		r++;
	}
}

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


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

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> H(N);
    for (int i = 0; i < N; i++) {
        cin >> H[i];
    }
    vector<int> cnts(N + 1, 0);
    for (int i = 0; i < N; i++) {
        if (H[i] >= H[i + 1]) cnts[i + 1] = cnts[i] + 1;
    }
    int res = 0;
    for (int i = 0; i < N; i++) {
        res = max(res, cnts[i]);
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 1024
N, M = gets.chomp.split.map(&:to_i)
count_m = Hash.new(0)

N.times{
    k, *a = gets.chomp.split.map(&:to_i)
    a.each_with_object(count_m) {|key, hash| hash[key] += 1}
}

p count_m.inject(0) {|sum, (_, value)| sum = value == N ? sum + 1 : sum}

Measured memory_bytes: 1788
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <ctime>
#define INF 1000000000
#define LINF 9000000000000000000
#define mod 1000000007
 
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rrep(i,n) for(int i=(n);i>=0;i--)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define rsort(x) sort(all(x));reverse(all(x))
#define pb push_back
#define mp make_pair
#define MOD(x) (x%(mod))
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pi;
 
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
 
bool debug=false;
/*---------------------------------------------------*/

int main(){
  int n,y;
  cin>>n>>y;
  rep(a,2001){
    rep(b,2001){
      if(n-a-b>=0&&10000*a+5000*b+(n-a-b)*1000==y){
	cout<<a<<" "<<b<<" "<<n-a-b<<endl;
	return 0;
      }
    }
  }
  cout<<-1<<" "<<-1<<" "<<-1<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <list>
#include <queue>
#include <cmath>
#include <numeric>
using namespace std;

int inf = (1 << 30);
int mod = 1e9 + 7;
int64_t inf64 = (1LL << 60);

template <typename T>
T gcd(T a, T b) {
    if(b == 0) return a;
    else return gcd(b, a % b);
}

template <typename T>
T lcm(T a, T b) {
    T g = gcd(a, b);
    return a / g * b;
}

bool check(vector<int> a, int index, int key){
    if(a[index] >= key) return true;
    else return false;
}

int lower_bound(vector<int> a, int key){
    int left = -1, right = a.size();
    while(right - left > 1){
        int mid = left + (left + right) / 2;
        if(check(a, mid, key)) right = mid;
        else left = mid;
    }
    return right;
}

int main(){

    int P, Q, R;
    cin >> P >> Q >> R;

    cout << min({P + Q, R + Q, P + R}) << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
int main() {
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	int N,x;
	int a[1001];
	cin>>N>>x;
	for(int i=0;i<N;i++)
		cin>>a[i];
	sort(a,a+N);
	vector<int> b(N);
  	for (int i = 0; i < N; i++) {
    	b[i] = min(x, a[i]);
    	x -= b[i];
  	}
  	b.back() += x;
  	int ans = 0;
  	for (int i = 0; i < N; i++) {
    	ans += (a[i] == b[i]);
  	}
  	cout << ans << '\n';	
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#define INFTY 1000000000
int count=0;

void merge(int *a,int left,int mid,int right){
  int n1,n2,l[500000],r[500000];
  int i,j,k;

  n1 = mid-left;
  n2 = right-mid;
  for(i=0;i<n1;i++) l[i] = a[left+i];
  for(i=0;i<n2;i++) r[i] = a[mid+i];
  l[n1] = INFTY;
  r[n2] = INFTY;
  i=0;
  j=0;
  
  for(k=left;k<right;k++){
    if(l[i]<=r[j]){
      count++;
      a[k] = l[i];
      i++;
    }
    else{
      count++;
      a[k] = r[j];
      j++;
    }
  }
}

void mergeSort(int *a, int left, int right){
  int mid;

  if(left+1<right){
    mid = (left+right)/2;
    mergeSort(a, left, mid);
    mergeSort(a, mid, right);
    merge(a, left, mid, right);
  }
}

int main(){
  int n,a[510000];
  int left,right;
  int i;

  scanf("%d",&n);
  for(i=0;i<n;i++) scanf("%d",&a[i]);
  left = 0;
  right = n;

  mergeSort(a,left,right);
  for(i=0;i<n;i++){
  printf("%d",a[i]);
  if(i!=n-1) printf(" ");
  else printf("\n");
  }
  printf("%d\n",count);
  
  return 0;
}



Measured memory_bytes: 6628
///not today

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

#define SZ(x) (int)(x).size()
#define pb push_back
#define ll long long
#define xmax(x, y) (x) = max((x), (y))
#define xmin(x, y) (x) = min((x), (y))
#define F first
#define S second
#define pii pair<int, int>
#define pll pair<long long, long long>
#define int long long
#define pipii pair<int, pair<int, int> >
#define pf push_front

int32_t main(){
    int n;
    cin >>n;
    int ans = 1, l[3] = {-1, -1, -1};
    for(int i = 0; i < n; i ++){
        int x;
        cin >>x;
        int cn = 0;
        for(int j = 0; j < 3; j ++){
            if(l[j] == x - 1){
                cn ++;
                if(cn == 1)
                    l[j] ++;
            }
        }
        ans = (ans * cn)% 1000000007;
    }
    cout <<ans <<endl;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int max = (int)Math.pow(n,0.5)+1;
        int ans = 1;
        for(int i = 2; i < max; i++){
            int pow = 2;
            while(Math.pow(i,pow) <= n){
                ans = Math.max(ans,(int)Math.pow(i,pow));
                pow++;
            }
        }
        System.out.println(ans);
    }
}



Measured memory_bytes: 21972
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main{

	public static void main(String args[]) throws IOException {
		Main m = new Main();
		m.Run();
	}

	public void Run() {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int x = n;
		System.out.print(n + ":");

		List<Integer> L = new ArrayList<Integer>();

		for(int i = 2;i <= x/2 + 1;) {
			if(x % i == 0) {
				x /= i;
				L.add(i);
			}else {
				i++;
			}
		}

		if(x != 1) {
			L.add(x);
		}

		L.stream().forEach(e->System.out.print(" "+e));

		System.out.println();
		scan.close();
	}
}


Measured memory_bytes: 32096
n = (input())
if n == "SUN":
         print(7)
elif n == "MON":
         print(6)
elif n == "TUE":
         print(5)
elif n == "WED":
         print(4)
elif n == "THU":
         print(3)
elif n == "FRI":
         print(2)
elif n == "SAT":
         print(1)


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

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

    int s = 0, w = 0;
  	cin>>s>>w;
  	if(s<=w)
      cout<<"unsafe\n";
  	else
      cout<<"safe\n";
    return 0;
}


Measured memory_bytes: 3652
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <queue>
#include <numeric>
#include <climits>
#include <functional>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
using ll = long long;
const ll mod = 1000000007;
string al = "abcdefghijklmnopqrstuvwxyz";
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n; cin >> n;
	int num[26] = { 0 };
	REP(i, 26) {
		num[i] = 100000;
	}
	REP(i, n) {
		int temp[26] = { 0 };
		string s; cin >> s;
		REP(j, s.size()) {
			REP(k, 26) {
				if (s[j] == al[k]) {
					temp[k]++;
				}
			}
		}
		REP(k, 26){
			num[k] = min(num[k], temp[k]);
		}
	}
	string str="";
	
	REP(k, 26) {
		REP(i, num[k]) {
			str += al[k];
		}
	}
	cout << str << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, x, N) for (int i = x; i < (N); i++)
#define swap(a, b) (a += b, b = a - b, a -= b)
using namespace std;
typedef long long ll;
int main()
{
    int A, B;
    cin >> A >> B;
    if (A <= B * 2)
    {
        cout << 0 << endl;
    }
    else
    {
        cout << A - B * 2 << endl;
    }
}


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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    char w[3];
    cin >> w;
    int cons = 0;
    for (int i = 0; i < 3; i++)
        if (!cons && w[i] == 'R')
            cons++;
        else if (w[i - 1] == 'R' && w[i] == 'R')
            cons++;
    cout << cons;

    return 0;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
#include <sys/types.h>
#include <unistd.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

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

using ll=long long;
using R=long double;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

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

const pid_t pid = getpid();
// Problem Specific Parameter:

// a_i >= 1 for i in range(n) k = 0
// dp[5010][k]

// a_1 a_2 a_3 a_4 a_5 a_6 a_7
// {1,2,3,4,5,6}

// 1 1 1 1 1 1
// 0 1 1 1 1 1 k = 1
// 1 1 1 1 0 1 k = 2
// 0 1 1 1 1 1 k = 3
 
// b_i <= \sum b_j + 1 0 の数
// b_i <= total - b_i + 1 0 の数
// 2 * b_i <= total + 1
// total = k

// b_i = k + 1 - c_i
// k + 1 

// total n * (k + 1)

int dp[55][2510];
int a[55];

int main(void){
	int n, k;
	cin >> n >> k;
	rep(i, n) cin >> a[i];

	const int upper = n + k * (n - 1);
	rep(i, n + 1) rep(j, upper + 1) dp[i][j] = -1;
	dp[0][0] = 0;

	rep(i, n)rep(j, upper+1){
		if(dp[i][j] == -1) continue;
		rep(c, a[i] + 1){
			const int b = k + 1 - c;
			if(b < 0) continue;
			if(2 * b > k + 1) continue;
			if(c < 0) continue;
			if(c > k + 1) continue;
			if(j + c <= upper) dp[i + 1][j + c] = c;
		}
	}

	if(dp[n][upper] == -1){
		puts("-1");
		return 0;
	}

	vector<int> tmp;
	int cur = upper;
	rrep(i,n){
		const int p = dp[i + 1][cur];
		tmp.push_back(k + 1 - p);
		cur -= p;
	}

	assert(cur == 0);
	reverse(begin(tmp), end(tmp));

	vector<int> ans_idx(k);
	{
		using pii = pair<int,int>;
		vector<pii> hoge;
		rep(i, n) hoge.push_back(pii(tmp[i], i));
		sort(rbegin(hoge), rend(hoge));
		vector<int> fuga;
		rep(i, n) rep(loop, hoge[i].first) fuga.push_back(hoge[i].second);
		
		int idx = 0;
		
		for(int i = 0; i < k; i += 2){
			ans_idx[i] = fuga[idx++];
		}

		for(int i = 1; i < k; i += 2){
			ans_idx[i] = fuga[idx++];
		}
	}

	vector<int> ans;
	rep(i, n) if(i != ans_idx[0]) ans.push_back(i);
	ans.push_back(ans_idx[0]);

	rep(i, k){
		int s = ans_idx[i];
		int g = (i + 1 == k ? -1 :ans_idx[i + 1]);
		rep(j, n){
			if(j == s or j == g) continue;
			ans.push_back(j);
		}
		if(g != -1) ans.push_back(g);
	}	

	reverse(begin(ans), end(ans));

	const int q = ans.size();
	cout << q << endl;
	rep(i, q) cout << (i?" ":"") << ans[i] + 1;
	cout << endl;

	return 0;
}

Measured memory_bytes: 768
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
string s,t;
bool make(){
  for(int i=0;i<t.size();i++){
    if(t[i]==s[0]){
      for(int j=i+1;j<t.size();j++){
	if(t[j]==s[1]){
	  int d = j - i;
	  int l = j;
	  int k;
	  for(k=2;k<s.size();k++){
	    l+=d;
	    if(l>=t.size()||s[k]!=t[l]) break;
	  }
	  if(k==s.size()) return true;
	}
      }
    }
  }
  return false;
}
int main(){
  int N;
  cin >> N;
  cin >> s;
  int count=0;
  for(int i=0;i<N;i++){
    cin >> t;
    if(make()) count++;
  }
  cout << count << endl;
  return 0;
} 
  

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

#define lf double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n; cin>>n;
	ll n2 = 1<<n;
	multiset<ll> s;
	s.ins(-1);
	rep(i, n2){
		ll temp; cin>>temp;
		s.ins(temp);
	}

	bool yes = true;
	vll btree(n2*2-1, 0);
	rep(i, n2*2-1){
		if (btree[i]!=0) continue;
		auto cur = s.end(); cur--;
		if (i!=0){
			cur = s.lower_bound(btree[i-1]);
			cur--;
		}
		if (*cur == -1){
			yes = false;
			break;
		}
		ll I = i;
		do{
			btree[I] = *cur;
			I = I*2+1;
		}while(I<n2*2-1);
		s.erase(cur);
	}

	if (yes){
		cout << "Yes\n";
	}else{
		cout << "No\n";
	}
	return 0;
}

Measured memory_bytes: 16640
#include <iostream>
#include <array>
#include <vector>
#include <iomanip>
#include <string>
#include <cmath>
#include <array>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;

typedef  pair<int,int> P;


int main(){
     int n,l;
          cin>>n>>l;
     vector<string>s(n);
     for(int i=0;i<n;++i){
          cin>>s[i];
     }
     sort(s.begin(),s.end());

     for(int i=0;i<n;++i){
          cout<<s[i];
     }
     cout<<endl;
}

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

int main() {
  string s; cin >> s;
  int x = stoi(s);
  int a = x/100; int b = x-a*100;
  if (1 <= a && a <= 12 && b <= 99) {
    if (1 <= b && b <= 12 && a <= 99) {
      cout << "AMBIGUOUS" << endl;
    } else {
      cout << "MMYY" << endl;
    }
  } else {
    if (1 <= b && b <= 12 && a <= 99) {
      cout << "YYMM" << endl;
    } else {
      cout << "NA" << endl;
    }
  }
}

Measured memory_bytes: 384
#include <iostream>
#include <numeric>
#include <set>
#include <utility>
#include <vector>

using namespace std;
using ll = long long;
using ld = long double;

template <typename T>
class UnionFind {
 private:
  vector<T> parent;
  vector<T> group_size;

 public:
  UnionFind(T size_) : parent(size_), group_size(size_, 1) {
    iota(parent.begin(), parent.end(), 0);
  }

  T root(T x) { return parent[x] == x ? x : parent[x] = root(parent[x]); }

  void merge(T x, T y) {
    x = root(x);
    y = root(y);
    if (x == y) return;

    if (group_size[x] < group_size[y]) swap(x, y);
    group_size[x] += group_size[y];
    parent[y] = x;
  }

  bool same(T x, T y) { return root(x) == root(y); }
  T size(T x) { return group_size[root(x)]; }
};

void solve(ll N, ll M, ll K, vector<ll> A, vector<ll> B, vector<ll> C,
           vector<ll> D) {
  // friends
  vector<set<int>> friends(N);
  UnionFind<int> u(N);
  for (int i = 0; i != M; ++i) {
    auto a = A[i] - 1;
    auto b = B[i] - 1;
    friends[a].insert(b);
    friends[b].insert(a);
    u.merge(a, b);
  }

  vector<set<int>> blocks(N);
  for (int i = 0; i != K; ++i) {
    auto c = C[i] - 1;
    auto d = D[i] - 1;
    blocks[c].insert(d);
    blocks[d].insert(c);
  }

  for (int i = 0; i != N; ++i) {
    auto ans = u.size(i) - 1;
    for (auto x : friends[i]) {
      if (u.same(i, x)) --ans;
    }
    for (auto x : blocks[i]) {
      if (u.same(i, x)) --ans;
    }
    cout << (i ? " " : "") << ans;
  }
  cout << endl;
}

int main() {
  ll N;
  cin >> N;
  ll M;
  cin >> M;
  ll K;
  cin >> K;
  vector<ll> A(M);
  vector<ll> B(M);
  for (int i = 0; i < M; i++) {
    cin >> A[i];
    cin >> B[i];
  }
  vector<ll> C(K);
  vector<ll> D(K);
  for (int i = 0; i < K; i++) {
    cin >> C[i];
    cin >> D[i];
  }
  solve(N, M, K, move(A), move(B), move(C), move(D));
  return 0;
}


Measured memory_bytes: 32896
def main():
    N, W = map(int, input().split())
    dp = [[0]*int(W+1) for _ in range(2)]
    for i in range(N):
        w, v = map(int, input().split())
        for j in range(W+1):
            dp[(i+1) % 2][j] = dp[i % 2][j]
        for j in range(W-w+1):
            dp[(i+1) % 2][j+w] = max(dp[i % 2][j] + v, dp[i % 2][j+w])
    print(dp[N % 2][W])


if __name__ == "__main__":
    main()


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

typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;
#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
#define next asdnext
#define prev asdprev
#define dump(x)  cout << #x << " = " << (x) << endl;	//debug
#define SZ(x) ((int)(x).size())
#define REP(i, n) for(ll i = 0; i < (n); i++)
#define REPR(i, n) for (ll i = (n); i >= 0; i--)
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define ps(s) cout << #s << endl;
#define pv(v) cout << (v) << endl;
#define ALL(a)  (a).begin(),(a).end()

ll num_of_digits(ll n, ll base) {
	ll cnt = 0;
	while (n > 0) {
		n /= base;
		cnt++;
	}
	return cnt;
}

int main() {
	ll n;
	cin >> n;
	ll cnt = 0;
	FOR(i, 1, n) {
		if (num_of_digits(i, 10) % 2 == 1) {
			cnt++;
		}
	}
	pv(cnt)
	return(0);
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#define T 1001
#define M 1000000007
#define E e[x][i]
#define S e[x].size()
using namespace std;
typedef long long ll;
ll func(int);
int N,s,t;
string n[T];
vector<int> e[T];
 
main(){
  int i;
  cin>>N;
  for(i=0;i<N;i++) cin>>n[i];
  for(i=0;i<N-1;i++) cin>>s>>t,e[s-1].push_back(t-1);
  cout<<func(0)%M<<endl;
}

ll func(int x){
  ll res=0,i;
  if(!S){
    if(n[x]=="E") return 1;
    return 2;
  }
  if(n[x][0]=='E'){
    res++;
    for(i=0;i<S;i++) res*=func(E);
    if(n[x]=="E?") res++;
  }
  else if(n[x][0]=='A'){
    for(i=0;i<S;i++) res+=func(E);
    if(n[x]=="A?") res++;
  }else{
    res++;
    for(i=0;i<S;i++) res*=(1+func(E));
    if(n[x]=="R") res--;
  }
  return res%M;
}

Measured memory_bytes: 1360
from collections import deque
while True:
    W,H = map(int,input().split())
    if W == 0: break
    src = [input() for i in range(H)]
    for y,row in enumerate(src):
        x = row.find('@')
        if x < 0: continue
        sx,sy = x,y
        break
    visited = [[0 for x in range(W)] for y in range(H)]
    visited[sy][sx] = 1
    q = deque([(sx,sy)])
    ans = 1
    while q:
        x,y = q.popleft()
        for dx,dy in zip([1,0,-1,0],[0,1,0,-1]):
            nx,ny = x+dx,y+dy
            if not(0 <= nx < W) or not(0 <= ny < H): continue
            if src[ny][nx] == '#' or visited[ny][nx]: continue
            visited[ny][nx] = 1
            ans += 1
            q.append((nx,ny))
    print(ans)

Measured memory_bytes: 6008
#include <bits/stdc++.h>
#include<iostream>
using namespace std;
 
int main() {
    int a,b,c,d,tmp,max;
    string s;
 	long long ans;
    a = b = c = d = ans = tmp = 0;
    

    cin >> a;
    vector<int>x(a);
  	for(int i =0;i < a;i++){
      cin >> x[i];
    }
  
   for(int i = 1;i < a;i++){
     if(x[i] < x[i-1]){
       tmp = x[i-1] - x[i];
       x[i] += tmp;
       ans += tmp;
     }
   }
   cout << ans;
}


Measured memory_bytes: 3960
A,B,C,D=map(int,input().split())
ans=''
for a in range(C-A) :
	ans=ans+'R'
for a in range(D-B) :
	ans=ans+'U'
for a in range(C-A) :
	ans=ans+'L'
for a in range(D-B) :
	ans=ans+'D'
ans=ans+'L'
for a in range(D-B+1) :
	ans=ans+'U'
for a in range(C-A+1) :
	ans=ans+'R'
ans=ans+'D'
ans=ans+'R'
for a in range(D-B+1) :
	ans=ans+'D'
for a in range(C-A+1) :
	ans=ans+'L'
ans=ans+'U'
print(ans)

Measured memory_bytes: 3064
H, W = map(int, input().split())
A = []
count = 0
for i in range(H):
    tmp = input() #入力は一文字として入ってくる
    if tmp == '.' * W:
        count += 1
    else:
        A.append(tmp)

skipp = []
for j in range(W):
    coucou = 0
    for i in range(H - count):
        if A[i][j] == '#':
            coucou = 1
            break
    if coucou == 0:
        skipp.append(j)
        
#出力
for i in range(H-count):
    for j in range(W):
        if j not in skipp:
            print(A[i][j], end = '')
    print()

Measured memory_bytes: 4468
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> iint;
typedef pair<ll,ll> llll;
#define ALL(x) (x).begin(),(x).end()
const ll zero = 0;
const ll one = 1;
const ll INF = 9223372036854775807; //10^18
const int inINF = 2147483647; //10^9
const ll MOD = 1000000007; //10^9+7
const ll MOD2 = 998244353;
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int main(){
    int N, ma, mb;
    cin >> N >> ma >> mb;
    vector<int> a(N), b(N), c(N);
    for (int i = 0; i < N; i++) {
        cin >> a[i] >> b[i] >> c[i];
    }
    if(N == 1){
        if(b[0] * ma - a[0] * mb != 0){
            printf("%d\n", -1);
            return 0;
        }
        printf("%d\n", c[0]);
        return 0;
    }

    vector<iint> F, L;
    vector<int> d(N);
    for (int i = 0; i < N; i++) {
        d[i] = b[i] * ma - a[i] * mb;
    }

    for (int i = 1; i < (1<<(N/2)); i++) {
        int tmpd, tmpc;
        tmpd = 0; tmpc = 0;
        for (int j = 0; j < N/2; j++) {
            if((i>>j) & 1){
                tmpd += d[j];
                tmpc += c[j];
            }
        }
        F.push_back(make_pair(tmpd, tmpc));
    }
    for (int i = 1; i < (1<<((N+1)/2)); i++) {
        int tmpd, tmpc;
        tmpd = 0; tmpc = 0;
        for (int j = 0; j < (N+1)/2; j++) {
            if((i>>j) & 1){
                tmpd += d[N/2+j];
                tmpc += c[N/2+j];
            }
        }
        L.push_back(make_pair(tmpd, tmpc));
    }

    sort(ALL(F));
    sort(ALL(L));
    int ans = inINF;
    int tmp;
    for (int i = 0; i < F.size(); i++) {
        int dd = - F[i].first;
        if(dd == 0) continue;
        auto itr = lower_bound(ALL(L), make_pair(dd, 0));
        iint v = *itr;
        if(v.first != dd) continue;
        tmp = v.second + F[i].second;
        ans = min(ans, tmp);
    }
    F.push_back(make_pair(inINF, inINF));
    L.push_back(make_pair(inINF, inINF));
    auto itf = lower_bound(ALL(F), make_pair(0, 0));
    iint vf = *itf;
    if(vf.first == 0){
        ans = min(ans, vf.second);
    }
    auto itl = lower_bound(ALL(L), make_pair(0, 0));
    iint vl = *itl;
    if(vl.first == 0){
        ans = min(ans, vl.second);
    }
    if(ans == inINF){
        printf("%d\n", -1);
        return 0;
    }
    printf("%d\n", ans);

}

Measured memory_bytes: 23704
#include<iostream>
#include<string>
#include<stdio.h>
#include <algorithm>
#include <set>
#include<map>
#include<vector>

using namespace std;

int main(){
    int n;
    cin >> n;
    unsigned long int x = 1;
    unsigned long int t = 10;
    for(int k = 1;k < 9;k++){
        t *= 10;
    }
    //cout << x << endl;
    t += 7;
    for(int i = 1;i <= n;i++){
        x = (x * i)%t ;
        
    }
    cout << x%t << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define int long long
#define all(a) a.begin(), a.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;
int h, w, d;
int a[310][310];
map<int, int> mp2;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> h >> w >> d;
    map<int, P> mp;
    rep(i, 0, h){
        rep(j, 0, w){
            cin >> a[i][j];
            a[i][j]--;
            mp[a[i][j]] = {i, j};
        }
    }
    rep(i, 0, d){
        mp2[i] = 0;
        for(int j = i + d; j < h * w; j += d){
            mp2[j] = mp2[j - d] + abs(mp[j - d].first - mp[j].first) + abs(mp[j - d].second - mp[j].second);
        }
    }
    int q;
    cin >> q;
    rep(i, 0, q){
        int l, r;
        cin >> l >> r;
        l--; r--;
        cout << mp2[r] - mp2[l] << endl;
    }
}

Measured memory_bytes: 13056
#include <iostream>
#define REP(i, a, n) for(int i = ((int) a); i < ((int) n); i++)
using namespace std;

int H, W, N;
char S[35][35];

bool ok(int i1, int i2, int i3, int i4) {
  bool used[35][35];
  char T[35][35];
  REP(i, 0, H) REP(j, 0, W) T[i][j] = S[i][j];
  swap(T[i1][i2], T[i3][i4]);
  REP(i, 0, H) REP(j, 0, W) {
    if(T[i][j] == '.') {
      for(int k = i - 1; k >= 0; k--) T[k + 1][j] = T[k][j];
      T[0][j] = '.';
    }
  }

  bool cont = true;
  while(cont) {
    REP(i, 0, H) REP(j, 0, W) used[i][j] = false;
    REP(i, 0, H) REP(j, 0, W) {
      if(T[i][j] == '.') continue;
      int f1 = true;
      REP(k, 1, N) if(i + k >= H || T[i + k][j] != T[i][j]) f1 = false;
      if(f1) REP(k, 0, N) used[i + k][j] = true;
      int f2 = true;
      REP(k, 1, N) if(j + k >= W || T[i][j + k] != T[i][j]) f2 = false;
      if(f2) REP(k, 0, N) used[i][j + k] = true;
    }
    cont = false;
    REP(i, 0, H) REP(j, 0, W) if(used[i][j]) T[i][j] = '.', cont = true;
    REP(i, 0, H) REP(j, 0, W) {
      if(T[i][j] == '.') {
        for(int k = i - 1; k >= 0; k--) T[k + 1][j] = T[k][j];
        T[0][j] = '.';
      }
    }
  }
  bool f = true;
  REP(i, 0, H) REP(j, 0, W) if(T[i][j] != '.' && !used[i][j]) f = false;
  return f;
}

int main(void) {
  cin >> H >> W >> N;
  REP(i, 0, H) cin >> S[i];

  bool ans = false;
  REP(i, 0, H) REP(j, 0, W) if(j + 1 < W) ans = ans || ok(i, j, i, j + 1);
  cout << (ans ? "YES" : "NO") << endl;

  return 0;
}

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

using namespace std;

typedef long long ll;
const ll INF = 1LL<<60;

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

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

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

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

    int N, M, P;
    cin >> N >> M >> P;

    vector<tuple<int, int, ll>> G(N);
    vector<vector<int>> go(N);
    vector<vector<int>> back(N);

    int tmp_A, tmp_B, tmp_C;
    for(int i = 0; i < M; i++){
        cin >> tmp_A >> tmp_B >> tmp_C;
        tmp_A--;
        tmp_B--;
        G.push_back(make_tuple(tmp_A, tmp_B, P-tmp_C));
        go[tmp_A].push_back(tmp_B);
        back[tmp_B].push_back(tmp_A);
    }

    vector<bool> visited_s(N);
    vector<bool> visited_g(N);

    for(int i = 0; i < N; i++){
        visited_s[i] = false;
        visited_g[i] = false;
    }

    queue<int> q_g;
    q_g.push(N-1);
    visited_g[N-1] = true;
    while(!q_g.empty()){
        int cur = q_g.front();
        q_g.pop();

        for(int i = 0; i < back[cur].size(); i++){
            if(visited_g[back[cur][i]] == true){
                continue;
            }
            else{
                q_g.push(back[cur][i]);
                visited_g[back[cur][i]] = true;
            }
        }
    }

    queue<int> q_s;
    q_s.push(0);
    visited_s[0]   = true;

    while(!q_s.empty()){
        int cur = q_s.front();
        q_s.pop();

        for(int i = 0; i < go[cur].size(); i++){
            if(visited_s[go[cur][i]] == true){
                continue;
            }
            else{
                q_s.push(go[cur][i]);
                visited_s[go[cur][i]] = true;
            }
        }
    }

    vector<bool> valid_node(N);
    for(int i = 0; i < N; i++){
        if(visited_s[i] && visited_g[i]){
            valid_node[i] = true;
        }else{
            valid_node[i] = false;
        }
    }

    vector<ll> cost(N);
    cost[0] = 0;
    for(int i = 1; i < N; i++){
        cost[i] = INF;
    }

    bool is_inf = false;

    bool updated = false;
    for(int k = 0; k < G.size(); k++){
        for(auto itr = G.begin(); itr != G.end(); itr++){//辺の数だけ
            updated = false;
            updated = chmin(cost[get<1>(*itr)], cost[get<0>(*itr)]+get<2>(*itr));

            if((updated == true && k == G.size()-1) && valid_node[get<1>(*itr)] == true){
                is_inf = true;
            }
        }
    }

    if(is_inf){
        cout << -1 << endl;
    }else{
        cout << max(-1*cost[N-1], 0LL) << endl;
    }

    return 0;
}



Measured memory_bytes: 640
n = int(input())
li = list(map(int,input().split()))
li2 = []
for i in range(n):
    li2.append(int(input()))

num ,a= 0,0
for i in range(len(li2)):
    while  True:
        if 1+a*li2[i]<=li[0]:
            num += 1
            a += 1
        else:
            a = 0
            break
print(num+li[1])

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();
		String op = sc.next();
		int b = sc.nextInt();

		if ("+".equals(op)){
			System.out.println(a+b);
		} else if ("-".equals(op)){
			System.out.println(a-b);
		}
	}

}


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

int main(){
	int a,b,A;
	char op;
	
	while(1){
		cin>>a>>op>>b;
		
		if(op=='+'){
			A=a+b;
		}else if(op=='-'){
			A=a-b;
		}else if(op=='*'){
			A=a*b;
		}else if(op=='/'){
			A=a/b;
		}else{
			break;
		}
		cout<<A<<endl;
	}
	return 0;
}

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

int main() {
  string s, ans = "No";
  cin >> s;
  if(s.at(0) == s.at(1) && s.at(2) == s.at(3) && s.at(1) != s.at(2)) ans = "Yes";
  if(s.at(0) == s.at(3) && s.at(2) == s.at(1) && s.at(1) != s.at(0)) ans = "Yes";
  if(s.at(0) == s.at(2) && s.at(1) == s.at(3) && s.at(1) != s.at(0)) ans = "Yes";
  cout << ans << endl;
}

Measured memory_bytes: 3612
package main

import (
	"fmt"
	"os"
	"bufio"
	"strings"
)

func checkVowel(text string) (string) {
	vowel := []string{"a", "e", "i", "o", "u"}

	for _, v := range vowel{
		if strings.Contains(text, v) {
			return "vowel"
		}
	}
	return "consonant"
}

func main(){
	stdin := bufio.NewScanner(os.Stdin)
	stdin.Scan()
	text := stdin.Text()

	result := checkVowel(text)
	fmt.Println(result)
}


Measured memory_bytes: 640
<?php
// https://atcoder.jp/contests/abc144/tasks/abc042_a
//整数A,B,Cが5,7,5の組み合わせであるかどうか判定


// fgets(STDIN)で標準入力,explode("",値)で入力を" "で切り分け配列化
$array = explode(" ", fgets(STDIN));

//5、7用それぞれのカウントを作成
$count5 = 0;
$count7 = 0;

//入力された数字を5か7であればそれぞれのカウントをすすめる
foreach($array as $num){
  switch ($num) {
    case 5:
      $count5++;
      break;
    case 7:
      $count7++;
      break;
  }
}

//5のカウントが2、かつ7のカウントが1であればYES
if($count5 == 2 && $count7 == 1){
  echo("YES\n");
}else{
  echo("NO\n");
}

Measured memory_bytes: 4604
n, m = map(int, input().split())
suma = 0
a = []
a.append(input().split())

for i in range(m):
    a[0][i] = int(a[0][i])
for i in range(m):
    suma = a[0][i] + suma

if n < suma:
    print(-1)
else:
    print(n-suma)



Measured memory_bytes: 9684
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <fstream>
#include <unordered_map>
#include <unordered_set>
#include <assert.h>
using namespace std;


#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007
#define P pair<ll, ll>

ll cnt[110];
int main() {
	ll n, k;
	cin >> n >> k;
	REP(i, k) {
		ll a;
		cin >> a;
		REP(i, a) {
			ll b;
			cin >> b;
			cnt[b]++;
		}
	}
	ll ans = 0;
	REPO(i, n) {
		if (cnt[i] == 0)ans++;
	}
	cout << ans << endl;
}



Measured memory_bytes: 3636
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define all(v) (v).begin(),v.end()
set<string> c;
const ll mod=1000000007;
const ll mod2=998244353;
const ll inf=100000000000000000;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
vector<int> dy={-1,0,1,0},dx={0,-1,0,1};
struct V{
   double x,y;
   //0で初期化
   V(double x=0.0,double y=0.0):x(x),y(y) {}
   V& operator+=(const V& v){ x+=v.x; y+=v.y;   return *this; }
   V operator+(const V& v) const{return V(*this)+=v;}
   //内積
   double dot(const V& v) const{return x*v.x+y*v.y;}
   //外積
   double cross(const V& v)const{return x*v.y-v.x*y;}
   //長さの２乗
   double norm2() const{return x*x+y*y;}
   //長さ
   double norm()const{return sqrt(norm2());}
   //象限(orthant)
   int ort() const{
     if(y>0)return x>0?1:2;
     else   return x>0?4:3;
   }
   //偏角ソートのための比較関数
   bool operator<(const V& v) const{//反時計回りを正
       int o=ort(),vo=v.ort();
       if(o!=vo)return o<vo;
       else return cross(v)>0;
       }
};
istream& operator>>(istream& is,V& v){//cinで読み込める
    is>>v.x>>v.y;  return is;
}
ostream& operator<<(ostream& os,const V& v){//出力
   os<<"("<<v.x<<","<<v.y<<")";return os;
}
int main(){
    int n;
    cin>>n;
    vector<V> v(n);
    for(int i=0;i<n;i++)cin>>v[i]; 
   // for(int i=0;i<n;i++)cout<<v[i]<<endl;
    sort(all(v));
    double ans=0.0;
    for(int i=0;i<n;i++){
        int r=i;
        V now;
        for(int j=0;j<n;j++){
            now+=v[r];
            ans=max(ans,now.norm());
            r=(r+1)%n;
        }
    }
    printf("%.12f\n",ans);
    return 0;
}


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

#define MAX_N 10000
#define INF 1000000000
int semi[MAX_N], dist[MAX_N], minx[MAX_N], kill[MAX_N];
pair<int, int>pa[MAX_N];
vector<pair<int,int>>x[MAX_N];
int N, C, A, B;
queue<int>Q;

int main() {
	cin >> N;
	for (int i = 1; i < N; i++) {
		cin >> C;
		if (C >= 1) {
			semi[i] = 1;
		}
	}
	for (int i = 0; i < N - 1; i++) {
		cin >> A >> B >> C;
		kill[B] = C;
		x[A].push_back(make_pair(B, C));
	}
	Q.push(0);
	for (int i = 0; i < MAX_N; i++) {
		dist[i] = INF;
		minx[i] = INF;
	}
	dist[0] = 0;
	while (!Q.empty()) {
		int to = Q.front(); Q.pop();
		for (int i = 0; i < x[to].size(); i++) {
			Q.push(x[to][i].first);
			dist[x[to][i].first] = dist[to] + 1;
		}
	}
	for (int i = 0; i < N; i++) {
		pa[i] = make_pair(dist[i], i);
	}
	sort(pa, pa + N);
	for (int h = N - 1; h >= 0; h--) {
		int i = pa[h].second;
		int sum1 = 0;
		for (int j = 0; j < x[i].size(); j++) {
			sum1 += minx[x[i][j].first];
		}
		if (semi[i] == 0) {
			minx[i] = min(kill[i], sum1);
			if (h == 0) {
				minx[i] = sum1;
			}
		}
		else {
			minx[i] = kill[i];
		}
	}
	cout << minx[0] << endl;
	return 0;
}

Measured memory_bytes: 3504
ans = {}
ans[[[0, 1], [1, 0], [1, 1]]] = "A"
ans[[[1, 0], [2, 0], [3, 0]]] = "B"
ans[[[0, 1], [0, 2], [0, 3]]] = "C"
ans[[[1,-1], [1, 0], [2,-1]]] = "D"
ans[[[0, 1], [1, 1], [1, 2]]] = "E"
ans[[[1, 0], [1, 1], [2, 1]]] = "F"
ans[[[0, 1], [1,-1], [1, 0]]] = "G"

arr = $stdin.read.split("\n")

m = arr.size
i = 0
while i < m
  pos = []
  8.times{|j|
    8.times{|k|
      if arr[i][k] == "1"
        pos << [j, k]
      end
    }
    i += 1
  }
  1.upto(3){|j|
    pos[j][0] -= pos[0][0]
    pos[j][1] -= pos[0][1]
  }
  pos.shift
  puts ans[pos]
  i += 1
end

Measured memory_bytes: 8712
#include <bits/stdc++.h>
          using namespace std;
          #define tani_nachi_ke  ios_base::sync_with_stdio(false); cin.tie(NULL);
          #define M_PI 3.14159265358979323846
          #define data data_
          #define ff first
          #define ss second
          int const N = 200009;
          long long fen[N];
          int n;
          void update(int id,long long val)
          {
            while(id <= n)
            {
                fen[id] = max(fen[id],val);
                id += (id&(-id));
            }
          }

          long long querry(int id)
          {
            long long ans = 0;
            while(id > 0)
            {
                ans = max(ans,fen[id]);
                id -= (id&(-id));
            }
            return ans;
          }
          int main()
          {
          // clock_t begin = clock();
          // #ifndef ONLINE_JUDGE
          // freopen("input.txt", "r", stdin);
          // freopen("output.txt", "w", stdout);
          // #endif
          tani_nachi_ke  

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

          for(int i = 0; i < n; i++)
          {
             long long temp = querry(h[i] - 1);
             update(h[i], temp + a[i]);
          }
          cout << querry(n) << endl;


          // #ifndef ONLINE_JUDGE 
          // clock_t end = clock();
          // cout<<endl<<double(end - begin) / CLOCKS_PER_SEC*1000<<" ms";
          // #endif 
          // return 0;
          }

Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
using vll = vector<vl>;
using Pll = pair<ll, ll>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(v) v.begin(), v.end()
#define sz(x) ((int) x.size())
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
const int MOD = 1e9+7;
const int INF = 2e9;
template<class T> void print(const T& t){ cout << t << endl; }
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 gcd(int a,int b){return b?gcd(b,a%b):a;}
ll dp[100007];
int main(){
  ll n;
  cin >> n;
  vl a(n);
  ll total = 0;
  rep(i, n){
    cin >> a[i];
    total += a[i];
    dp[a[i]]++;
  }
  ll q;
  cin >> q;
  rep(i,q){
    ll b, c;
    cin >> b >> c;
    total += (c - b) * dp[b];
    print(total);
    dp[c] += dp[b];
    dp[b] = 0;
  }
}

Measured memory_bytes: 4788
use std::io::BufRead;
fn main() {
    let stdin = std::io::stdin();
    let mut lines: Vec<Vec<i64>> = stdin
        .lock()
        .lines()
        .map(|l| {
            l.unwrap()
                .split_whitespace()
                .map(|w| w.parse().unwrap())
                .collect()
        })
        .collect();
    let (n, k, mut al, mut fl) = (lines[0][0], lines[0][1], lines.remove(1), lines.remove(1));
    if al.iter().sum::<i64>() <= k {
        println!("0");
        return;
    } else {
        al.sort();
        al.reverse();
        fl.sort();
        let mut list: Vec<_> = al.iter().zip(fl.iter()).collect();
        let mut lp: i64 = 1;
        let mut rp: i64 = 1 << 60;
        let mut mp: i64 = (lp + rp) / 2;
        while (lp != mp) || (mp != rp) {
            let cnt: i64 = list
                .iter()
                .filter(|&&(a, f)| (a * f) > mp)
                .map(|&(a, f)| a - (mp / f))
                .sum();
            if k < cnt {
                lp = mp + 1;
            } else {
                rp = mp;
            }
            mp = (lp + rp) / 2;
        }
        println!("{}", mp);
    }
}


Measured memory_bytes: 13420
#include<bits/stdc++.h>
using namespace std;
int main()
{
  string s;
  int n, ret = 0;
  cin >> s;
  cin >> n;
  while(n--){
    string buff;
    cin >> buff;
    buff += buff;
    ret += buff.find(s) != string::npos;
  }
  cout << ret << endl;
}

Measured memory_bytes: 1212
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define show(x) {for(auto i: x){cout << i << " ";} cout << endl;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
  string S;
  cin >> S;
  bool bl = false;
  rep(i, 2) {
    if (S[i] != S[i+1]) bl = true;
  }
  puts(bl ? "Yes" : "No");
  return 0;
}

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

int main() {
    int n;
    cin >> n;
    int64_t V = 0, E = 0;
    
    for (int64_t i = 1; i <= n; i++) V += i * (n - i + 1);
    
    for (int i = 0; i < n - 1; i++) {
        int64_t a, b;
        cin >> a >> b;
        if (a > b) swap(a, b);
        E += a * (n - b + 1);
    }
    cout << V - E << "\n";
    return 0;
}


Measured memory_bytes: 3600
#include <iostream>
#include <string>

using namespace std;

inline int popcount(int x) { return __builtin_popcount(x); }

inline int f(int x) {
  int res = 0;
  while (x) {
    x = x % popcount(x);
    res++;
  }
  return res;
}

int r[200001][2];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  string s;
  cin >> n >> s;
  int pc = 0;
  for (char c : s) pc += c - '0';
  const int pc0 = pc + 1;
  const int pc1 = pc - 1;

  int xr[2] = {0};
  int k0 = 1;
  int k1 = 1;
  for (int i = n - 1; i >= 0; i--) {
    if (s[i] == '1') {
      xr[0] += k0;
      xr[0] %= pc0;
      if (pc1 > 0) {
        xr[1] += k1;
        xr[1] %= pc1;
      }
    }
    r[i][0] = k0;
    r[i][1] = k1;
    k0 = (2 * k0) % pc0;
    if (pc1 > 0) {
      k1 = (2 * k1) % pc1;
    }
  }

  for (int i = 0; i < n; i++) {
    int xi = 0;
    if (s[i] == '1') {
      if (pc == 1) {
        cout << 0 << endl;
        continue;
      }
      xi = (xr[1] - r[i][1] + pc1) % pc1;
    } else {
      xi = (xr[0] + r[i][0] + pc0) % pc0;
    }
    cout << f(xi) + 1 << endl;
  }
  return 0;
}


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

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

const int INF = 2e9;
const int MOD = 1e9+7;
const int MAX = 1e5+10;
const lint LNF = 2e18;

int n, A[MAX], S[MAX];
int T[2*MAX];
void clear(){ for(int i=0; i<=2*n+1; i++) T[i] = 0; }
void upt(int p){
	p += n+1;
	for(; p<=2*n+1; p+=p&(-p)) T[p]++;
}
int get(int p){
	int r = 0; p += n+1;
	for(; p>0; p-=p&(-p)) r+=T[p];
	return r;
}

bool check(int x){
	for(int i=1; i<=n; i++) S[i] = S[i-1] + (A[i]<x ? -1 : 1);
	clear();
	lint cnt = 0;
	for(int i=1; i<=n; i++){
		upt(S[i-1]);
		cnt += get(S[i]);
	}
	return 1LL*n*(n+1)/2 <= cnt*2;
}

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

	cin>>n;
	for(int i=1; i<=n; i++) cin>>A[i];

	int s = 0, e = 1e9;
	while(s<e){
		int m = (s+e+1)/2;
		if(check(m)) s = m;
		else e = m-1;
	}
	cout<<s<<'\n';

	return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <vector>
#include <stdlib.h>
#include <utility>

using namespace std;

int main()
{

	string str;
	getline(cin, str);
	
vector<string> vStr;

	while (str.find(' ') != -1 )
	{
		vStr.push_back(str.substr(0,str.find(' ')));
		str.erase(0, str.find(' ') + 1);
	}
	vStr.push_back(str);

cout << stoi(vStr.at(0)) * stoi(vStr.at(1)) << " " << stoi(vStr.at(0)) * 2 + stoi(vStr.at(1)) * 2 << endl;

return 0;

}

Measured memory_bytes: 1200
n, m, X, Y = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
cnt = 0
for z in range(-100, 101):
    if X < z and z <= Y and max(x) < z and min(y) >= z:
        print("No War")
        break
    else:
        cnt += 1
        if cnt == 201:
            print("War")
            break

Measured memory_bytes: 9184
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>

using namespace std;

pair<int,int> dp[101][50501];

bool ge(pair<int,int>p1,pair<int,int>p2){
	if(p1.first==0&&p1.second==0)return 1;
	if(p2.first==0&&p2.second==0)return 0;
	if(p1.first > p2.first)return 0;
	if(p1.first < p2.first)return 1;
	if(p1.second < p2.second)return 0;
	return 1;
}


int main(){
	int n;
	int x;
	pair<int,int> p1,p2;	
	while(1){
		cin >> n;
		if(n==0)break;
		for(int i=0;i<101;i++){
			for(int j=0;j<50001;j++){
				dp[i][j]=make_pair(0,0);
			}
		}
		vector<int> v(n+1,0);
		for(int i=1;i<=n;i++){
			cin >> v[i];
		}
		for(int i=1;i<=n;i++){
			x = (v[i]-1)%1000+1;
			if(x<=500){
				for(int j=0;j<x;j++){
					dp[i][j] = dp[i-1][j];
				}
				for(int j=0;j<50000;j++){
					if(j==0&&dp[i-1][j]==make_pair(0,0)){
						dp[i][j+500-x] = make_pair(1,v[i]);
						dp[i][j+500-x] = max(dp[i][j+500-x],dp[i-1][j+500-x],ge);
					}else{
						if(dp[i-1][j]!=make_pair(0,0)){
							dp[i][j+500-x] = dp[i-1][j];
							dp[i][j+500-x].first +=1;
							dp[i][j+500-x].second +=v[i];
							dp[i][j+500-x] = max(dp[i][j+500-x],dp[i-1][j+500-x],ge);
						}else{
							dp[i][j+500-x] = dp[i-1][j+500-x];
						}
					}
				}
			}else{
				for(int j=0;j<50000;j++){
					p1 = make_pair(0,0);
					p2 = make_pair(0,0);
					if(j-(1000-x)>=0){
						if(dp[i-1][j-(1000-x)]!=make_pair(0,0)){
							p1 = dp[i-1][j-(1000-x)];
							p1.second += v[i];
						}
					}
					if(dp[i-1][j+x-500]!=make_pair(0,0)){
						p2 = dp[i-1][j+x-500];
						p2.first +=1;
						p2.second +=v[i];
					}
					dp[i][j] = dp[i-1][j];
					if(j-(1000-x)==0){
						if(dp[i-1][j]==make_pair(0,0)){
							dp[i][j]=make_pair(0,v[i]);
						}else{
							dp[i][j]=max(dp[i-1][j],make_pair(0,v[i]),ge);
						}
					}
					dp[i][j] = max(dp[i][j],p1,ge);
					dp[i][j] = max(dp[i][j],p2,ge);
					if(j==0&&dp[i][j].first==0){
						dp[i][j] = make_pair(0,0);
					}
				}
			}
		}
		pair<int,int> mx = make_pair(0,0);
		for(int j=0;j<50000;j++){
			mx = max(mx,dp[n][j],ge);
		}
		if(mx.first==0){
			cout << 0 << " " << 0 << endl;
		}else{
			cout << mx.first << " " << mx.second << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 42920