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

int main(){
    int N, K; cin >> N >> K;
    int a[N];
    int b[200010] = {};
    for(int i = 0; i < N; i++){
        cin >> a[i];
        b[a[i]]++;
    }
    // for(int i = 0; i < 200010; i++){
    //     cout << b[i] << ' ';
    // }
    // cout << endl;
    sort(b,b+N,greater<int>());
    // for(int i = 0; i < 200010; i++){
    //     cout << b[i] << ' ';
    // }
    // cout << endl;
    long long ans = 0;
    for(int i = K; i < 200010; i++){
        ans += b[i];
    }
    cout << ans << endl;
    

    

    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>

int dx[] = {-1,0,1,0},dy[] = {0,-1,0,1};
int x[1000],y[1000];
int Mw,Mn,me,ms;
using namespace std;


int main(){

  int n,p,d;
  while(1){
    Mw = ms = 0;
    Mn = me = 0;
    x[0] = y[0] = 0;
    cin >> n;
    if(n == 0)break;

    for(int i = 1; i < n ; i++){
     
      cin >> p >> d;
      x[i] = x[p] + dx[d];
      y[i] = y[p] + dy[d];

      Mw = min(x[i],Mw);
      Mn = max(y[i],Mn);
      ms = min(y[i],ms);
      me = max(x[i],me);
    }
    cout << me - Mw +1 << " ";
    cout << Mn - ms +1 << endl;
   }
  return 0;
}

Measured memory_bytes: 1164
n,h=map(int,input().split())
a,b=[],[]
for i in range(n):
    j,k=map(int,input().split())
    a.append(j)
    b.append(k)
am=max(a)
bm=[]
for i in b:
    if am<i:bm.append(i)
if sum(bm)<h:print(len(bm)+(h-sum(bm)+am-1)//am)
else:
    bm.sort()
    ans=0
    while h>0:
        h-=bm.pop(-1)
        ans+=1
    print(ans)

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

int main(){
 string s;
  cin >> s;
  if(s=="Sunny")cout << "Cloudy"<<endl;
  else if(s=="Cloudy")cout << "Rainy"<<endl;
  else cout << "Sunny"<<endl;
}

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

int main()
{
  int n, m;
  cin >> n;

  int min1 = 200000;
  int cnt = 0;
  for(int i = 0; i < n; i++){
    cin >> m;
    if(min1 >= m){
      cnt++;
    }
    min1 = min(min1, m);
  }
  cout << cnt << endl;    
}

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

namespace AtCorder
{
	public class Program
	{
		static void Main(string[] args)
		{
			int[] hwd = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
			int h = hwd[0];
			int w = hwd[1];
			int d = hwd[2];

			Tuple<int, int>[] a = new Tuple<int, int>[h * w];
			for (int i = 0; i < h; i++) {
				int[] aa = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
				for (int j = 0; j < w; j++) {
					a[aa[j] - 1] = new Tuple<int, int>(i + 1, j + 1);
				}

			}

			int[] p = new int[h * w];
			for (int i = 0; i < h * w; i++) {
				if (i / d == 0) {
					p[i] = 0;
				} else {
					var dst = a[i];
					var src = a[i - d];
					p[i] = Math.Abs(src.Item2 - dst.Item2) + Math.Abs(src.Item1 - dst.Item1)
						+ p[i - d];
				}
			}

			int q = int.Parse(Console.ReadLine());
			for (int i = 0; i < q; i++) {
				int[] lr = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
				Console.WriteLine(p[lr[1] - 1] - p[lr[0] - 1]); 
			}
		}
	}
}


Measured memory_bytes: 22964
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;

int main()
{
    int n;
    cin >> n;
    vector<int> checked(100005);
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        if (checked[a] > 0)
        {
            ans++;
        }
        checked[a]++;
    }
    cout << n - ans - ans % 2 << endl;
    return 0;
}

Measured memory_bytes: 3788
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  long int h[n];
  for(int i=0;i<n;i++)
    cin>>h[i];
  long int a[n]={};
  a[0]=h[0];
  a[1]=abs(h[1]-h[0]);
  for(int i=2;i<n;i++)
  {
    if(i==2)
      a[i]=min(abs(h[i]-a[i-2]),a[i-1]+abs(h[i]-h[i-1]));
    else
      a[i]=min(a[i-2]+abs(h[i]-h[i-2]),a[i-1]+abs(h[i]-h[i-1]));
  }
  cout<<a[n-1];
}

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

using namespace std;

typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = (ll)1e9 + 7;

int main()
{
  int N; scanf("%d", &N);
  vector<string> s(2);
  cin >> s[0] >> s[1];
  ll ans = (s[0][0] == s[1][0]) ? 3 : 6;
  int start = (ans == 3) ? 1 : 2;
  int state = (ans == 3) ? 0 : 1;
  for (int i = start; i < N; ) {
    if (s[0][i] == s[1][i]) {
      // --> 0
      if (state == 0) {
        // 0 --> 0
        ans = (ans * 2) % MOD;
      }
      else {
        // 1 --> 0
      }
      ++i;
      state = 0;
    }
    else {
      // --> 1
      if (state == 0) {
        // 0 --> 1
        ans = (ans * 2) % MOD;
        state = 1;
      }
      else {
        // 1 --> 1
        ans = (ans * 3) % MOD;
        state = 1;
      }
      i += 2;
      state = 1;
    }
  }
  printf("%lld\n", ans);
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <limits>
#include <algorithm>
#include <functional>

#include <vector>
#include <set>
#include <map>

using namespace std;

map<int, long long> num_count;
vector<int> num_order;

map<int, long long> count1;
map<int, long long> count2;

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

	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		int a;
		cin >> a;

		num_count[a]++;
		num_order.push_back(a);
	}

	long long accum = 0;
	for (pair<int, long long> e : num_count)
	{
		long long count1_val = e.second * (e.second - 1LL) / 2LL;
		long long count2_val = (e.second - 1) * (e.second - 2LL) / 2LL;
		count1[e.first] = count1_val;
		count2[e.first] = count2_val;
		accum += count1_val;
	}

	for (int i = 0; i < num_order.size(); i++)
	{
		cout << accum - count1[num_order[i]] + count2[num_order[i]] << "\n";
	}

	return 0;
}

Measured memory_bytes: 26100
#include <stdio.h>
#include <string.h>
#include <ctype.h>

int main(){
    char w[10], t[1000];
    int i, count = 0;
    
    scanf("%s", w);
    
    while (1) {
        scanf("%s", t);
        
        if(strcmp(t, "END_OF_TEXT" ) == 0) break;
        for (i = 0; t[i] != '\0'; i++) t[i] = tolower(t[i]);
        if (strcmp(w, t) == 0) count++;
    }
    
    printf("%d\n", count);
    return 0;
}

Measured memory_bytes: 552
fun main(args: Array<String>) {
    val (n, k) = readLine()!!.split(' ').map(String::toInt)
    val dp = Array(n+10){Array(n+10){Array<Int>(k + 10){-1}}}
    val mod = 1000000000 + 7
    dp[0][0][0] = 1
    dp[0][1][2] = 1
    // i n -> 0, j 0 -> 増減 < i+1, k k -> 0
    fun calc(i: Int, j: Int, k: Int): Int{
        if(k < 0) return 0
        if(i < j - 1) return 0
        if(j < 0) return 0
        if(i < 0) return 0
        if(dp[i][j][k] != -1) return dp[i][j][k]
        if(i == 0) return 0

        val ret = (((2 * j + 1).toLong() * calc(i-1, j, k - 2 * j) +
                (j + 1) * (j + 1).toLong() * calc(i-1, j + 1, k - 2 * j) +
                calc(i-1, j - 1, k - 2 * j)) % mod).toInt()
        dp[i][j][k] = ret
        return ret
    }
    val ret = calc(n-1, 0, k)
    print(ret)
}

Measured memory_bytes: 87340
#define _USE_MATH_DEFINES
#include <iostream>
#include <memory>
#include <memory.h>
#include <fstream>
#include <cmath>
#include <math.h>
#include <numeric>
#include <vector>
#include <stack>
#include <string>
#include <queue>
#include <sstream>
#include <cstdlib>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <map>
#include <set>
#include <iomanip>
#include <list>
#include <cctype>
#include <algorithm>
#include <complex>
using namespace std;

typedef complex<double> xy_t;
typedef pair<xy_t, xy_t> line;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<double, double> Pd;
typedef pair<int, P> PP;
typedef pair<int, PP> PPP;
const ll INF = 1LL << 50;
const double EPS = 1E-10;

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

const int MAX = 10010;
P ACM[100010];
vector<int> ICPC[MAX];
int dis[100];

int main(){
	int AN, BN, R;
	int x, y, d;

	while(cin >> AN >> BN >> R&& (AN || BN)){

		for(int i = 0; i <= 4 * R; i++){
			int d2 = (16 * R * R - i * i);
			int d = ((sqrt((double)d2)) + 0.5);
			if(d * d > d2) d--;
			dis[i]=d;
		}
		rep(i, AN){
			cin >> ACM[i].first >> ACM[i].second; 
		}
		int cnt = 0;
		rep(i, BN){
			cin >> x >> y;
			ICPC[x].push_back(y);
		}
		
		rep(i, MAX) sort(ICPC[i].begin(), ICPC[i].end());
	
		rep(i, AN){
			x = ACM[i].first;
			y = ACM[i].second;
			for(int j = x - 4 * R; j <= x + 4 * R; j++){
				if(j < 0 || j >= 10000) continue;
				d = dis[abs(j - x)];
				cnt += upper_bound(ICPC[j].begin(), ICPC[j].end(), y+d) - 
						lower_bound(ICPC[j].begin(), ICPC[j].end(), y-d);
			}
		}
		cout << cnt << endl;
		rep(i, MAX){
			ICPC[i].clear();
		}
	}
	return 0;
}

Measured memory_bytes: 0
/*
title:

url:
*/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <queue>
#include <limits>
#include <string>
#include <utility>
#include <cstring>
#include <map>
#include <cmath>
#include <iterator>

using namespace std;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define INF 1000000007

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

int main()
{
    int N;
    cin >> N;
    vector<int> data;
    rep(i, N)
    {
        int tmp;
        cin >> tmp;
        data.push_back(tmp);
    }
    sort(data.begin(), data.end());
    int ans = 0;
    for (int i = 0; i < N - 1; i++)
    {
        ans += data[i];
    }
    ans += data[N - 1] / 2;
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int N;
int a[2000000];
vector<int> lungs;
int main() {
    cin >> N;
    for(int i = 0; i < (1 << N); i++) {
        cin >> a[i];
        bool childdie = false;
        for(int j = 0; j < N; j++) {
            if(!((1 << j) & i)) continue;
            int child = (i & (~(1 << j)));
            if(a[i] == 0) {
                if(a[child] == 1) {
                    cout << -1 << endl;
                    return 0;
                }
            } else {
                if(a[child] == 1) {
                    childdie = true;
                }
            }
        }
        if(a[i] == 1 && !childdie) {
            lungs.push_back(i);
        }
    }
    if(lungs.empty()) {
        cout << -1 << endl;
        return 0;
    }
    cout << lungs.size() << endl;
}


Measured memory_bytes: 7816
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;

int main()
{
    int n;
    cin>>n;
    vector<int> b(n-1);
    for(int i=0;i<n-1;i++) cin>>b[i];

    vector<int> c(n);
    c[0]=b[0];c[n-1]=b[n-2];
    int v=c[0]+c[n-1];
    for(int i=1;i<=n-2;i++){
        c[i]=min(b[i-1],b[i]);
        v+=c[i];
    }

    cout<<v<<endl;

	return 0;
}


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

int main() {
	int n;cin>>n;
	vector<int> v(n);
	for (int i = 0; i < n; ++i) cin >> v[i];
	sort(v.begin(), v.end());
	cout << v[n-1] - v[0] << endl;
	return 0;
}

Measured memory_bytes: 256
//#pragma GCC optimize("-Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
//#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
//#pragma GCC target("avx2")  //Enable AVX
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef tree<pair<ll,ll>,null_type,less<pair<ll,ll>>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
//order_of_key(x) : number of items less than x
//find_by_order(x) : iterator to x

#define mem(dp,a)           memset(dp,a,sizeof dp)
#define rep(i,a,b)          for(ll i=a;i<b;i++)
#define pb(x)               push_back(x)
#define mp(x,y)             make_pair(x,y)
#define fastio              ios_base::sync_with_stdio(false);cin.tie(NULL)
#define F                   first
#define S                   second
#define all(v)              (v).begin(),(v).end()

const ld pi=3.14159265359;
ll INF=1e18+10;
ll MOD=998244353;
ll mod=1e9+7;

inline ll add(ll a,ll b,ll m){
    if((a+b)>=m)return (a+b)%m;
    return a+b;
}

inline ll mul(ll a,ll b,ll m){
    if((a*b)<m)return a*b;
    return (a*b)%m;
}

ll expo(ll a,ll b,ll m){
    if(b<0)return expo(expo(a,m-2,m),-b,m);
    ll res=1;
    while(b>0){
        if(b&1)res=mul(res,a,m);
        a=mul(a,a,m);
        b=b/2;
    }
    return res;
}

int main()
{
    ll x,k,d;cin>>x>>k>>d;
    x = abs(x);
    ll xneg = x-k*d;
    ll i = (x + d - 1)/d;
    if(i <= k){
        x -= i*d;
        int par = (i&1)^(k&1);
        if(par == 0)cout<<abs(x)<<endl;
        else cout<<abs(x+d)<<endl;
    } else cout<<xneg<<endl;
}


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

int main()
{
	int a, b, ans;

	cin >> a >> b;

	if (b == 100)
	{
		ans = a * 1000 + b;
	}
	else if (b > 9)
	{
		ans = a * 100 + b;
	}
	else
	{
		ans = a * 10 + b;
	}

	for (int i = 1; i*i <= 100100; i++)
	{
		if (ans == i * i)
		{
			cout << "Yes" << endl;
			return 0;
		}
	}

	cout << "No" << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long ll;
#define REP(i,n) for(int i = 0;i < (n);i++)
#define rep(i,m,n) for(int i = (m);i < (n);i++)
#define P pair<int,int>
#define pb push_back
#define mk make_pair
using namespace std;
#define Vec(a) vector <int> a
const int INF = 1 << 20;
const int MOD = 1e9+7;





int main(){
  int n;
  cin >> n;
  bool f = true;
  ll a = 0;
  REP(i,n){
    string s;
    cin >> s;
    if(s == "A"){
      a++;
    }
    else{
      a--;
    }
    if(a < 0){
      cout << "NO" << endl;
      f = false;
      return 0;
    }
  }
  if(a == 0)
    cout << "YES" << endl;
  
  else 
    cout << "NO" << endl;
  return 0;
}



Measured memory_bytes: 3140
#include <vector>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <deque>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
#define rep(i, n) for(int i = 0; i<n; i++)
#define rep_s(i, start, n) for(int i= start;  i<n; i++)
#define ALL(a) (a).begin(), (a).end()
string alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

/*
using edge = struct {int to; ll cost;};
vector<edge> tree[limit];
ll depth[limit];

void dfs(int v, int p, ll d){
  depth[v] = d;
  //cout <<"v: " << v << endl;
  for (auto &e: tree[v]){
    //cout << "e.to: " << e.to << endl;
    if (e.to == p) continue;
    dfs(e.to, v, d+e.cost);
  }
}
*/

int main(void){
  int N;
  cin >> N;
  int A, B, C, D;
  A = N/1000, B = N/100 -A*10; C = N/10 - A*100 - B*10; D = N-A*1000-B*100-C*10;
  //cin >> A >> B >> C>> D;
  int ans;
  //cout <<"A: " << A << ", B:" << B << ", C:" << C << endl;
  if (A+B+C+D == 7) {
    cout << A << "+" <<B<<"+"<<C<<"+"<<D<<"="<<7;
    return 0;
  } else if (A+B+C-D == 7) {
    cout << A << "+" <<B<<"+"<<C<<"-"<<D<<"="<<7;
    return 0;
  }
  else if (A+B-C+D == 7) {
    cout << A << "+" <<B<<"-"<<C<<"+"<<D<<"="<<7;
    return 0;
  }
  else if (A+B-C-D == 7) {
    cout << A << "+" <<B<<"-"<<C<<"-"<<D<<"="<<7;
    return 0;
  }
  else if (A-B+C+D == 7) {
    cout << A << "-" <<B<<"+"<<C<<"+"<<D<<"="<<7;
    return 0;
  }
  else if (A-B+C-D == 7) {
    cout << A << "-" <<B<<"+"<<C<<"-"<<D<<"="<<7;
    return 0;
  }
  else if (A-B-C+D == 7) {
    cout << A << "-" <<B<<"-"<<C<<"+"<<D<<"="<<7;
    return 0;
  }
  else if (A-B-C-D == 7) {
    cout << A << "-" <<B<<"-"<<C<<"-"<<D<<"="<<7;
    return 0;
  }


}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>

using namespace std;
using ll = long long int;
#define rep(i,n) for(int i = 0; i < n; i++)
#define FOR(i, a, b)  for(int i = (a); i < (b) ; i++)
#define pb push_back
#define SORT(v,n) sort(v, v+n)
#define ALL(x) (x).begin(),(x).end()
#define debug(x) cerr << #x << ": " << x << '\n'
#define elif else if
#define itn ll
#define int ll
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
int dx[8] = { 1, 0, -1, 0, 1, -1, -1, 1 };
int dy[8] = { 0, 1, 0, -1, 1, 1, -1, -1 };
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;

class Disjoint {
public:
	Disjoint(){}
	Disjoint(int size) {
		p.resize(size, 0);
		rank.resize(size, 0);
		int i;
		rep(i, size) makeSet(i);
	}

	bool same(int x, int y) {
		return findSet(x) == findSet(y);
	}

	void makeSet(int x) {
		p[x] = x;
		rank[x] = 0;
	}
	void unite(int x, int y) {
		link(findSet(x), findSet(y));
	}
	void link(int x, int y) {
		if (rank[x] > rank[y]) {
			p[y] = p[x];
		}
		else {
			p[x] = p[y];
			if (rank[x] == rank[y])
				rank[y]++;
		}
	}
	int findSet(int x) {
		if (p[x] != x) {
			p[x] = findSet(p[x]);
		}
		return p[x];
	}
private:
	vector<int> p,rank;
};

signed main() {
	ios::sync_with_stdio(false);
	int n, q;
	cin >> n >> q;
	Disjoint ds = Disjoint(n);
	rep(i, q) {
		int c, x, y;
		cin >> c >> x >> y;
		if (c == 0) {
			ds.unite(x, y);
		}elif(c == 1) {
			if (ds.same(x, y)) cout << 1 << '\n';
			else cout << 0 << '\n';
		}
	}
	return 0;
}


Measured memory_bytes: 3360
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
using namespace std;
int main() {
  int n, ans, k, t[6];
  vector< pair<int, int> > T;
  while (cin >> n, n) {
    for (int i = 0; i < n; ++i) {
      scanf("%d:%d:%d %d:%d:%d",&t[0],&t[1],&t[2],&t[3],&t[4],&t[5]);
      T.push_back(make_pair(t[0]*3600+t[1]*60+t[2], 1));
      T.push_back(make_pair(t[3]*3600+t[4]*60+t[5], -1));
    }
    ans = 0;
    k = 0;
    sort(T.begin(), T.end());
    for (int i = 0; i < 2*n; ++i) {
      k += T[i].second;
      ans = max(ans, k);
    }
    cout << ans << endl;
    T.erase(T.begin(), T.end());
  }
  return 0;
}


Measured memory_bytes: 3260
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		int cnt = 0;
		for(int i=0;i<N;i++){
			if(X[i] * X[i] + Y[i] * Y[i] <= D * D) cnt++;
		}
		Console.WriteLine(cnt);
	}
	int N;
	long D;
	long[] X,Y;
	public Sol(){
		var d = ria();
		N = d[0]; D = d[1];
		X = new long[N];
		Y = new long[N];
		for(int i=0;i<N;i++){
			d = ria();
			X[i] = d[0]; Y[i] = d[1];
		}
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}


Measured memory_bytes: 43588
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
namespace AtCoder
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }

        static void Main(string[] args)
        {
            SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            var N = Sarray()[0];
            var Ai = Sarray();
            var Aia = new long[Ai.Length + 2];
            var dst = new long[Ai.Length + 1];
            for (var i = 0; i < Ai.Length; ++i)
            {
                Aia[i + 1] = Ai[i];
                dst[i] = Abs(Aia[i + 1] - Aia[i]);
            }
            dst[Ai.Length] = Abs(Aia[Aia.Length - 1] - Aia[Aia.Length - 2]);
            var rui = new long[dst.Length + 1];
            for (var i = 1; i < dst.Length + 1; ++i)
                rui[i] = rui[i - 1] + dst[i - 1];
            for (var i = 0; i < Ai.Length; ++i)
            {
                var ans = 0L;
                ans += rui[i];
                ans += rui[rui.Length - 1] - rui[i + 2];
                ans += Abs(Aia[i + 2] - Aia[i]);
                WriteLine(ans);
            }
            Out.Flush();
        }
    }
}

Measured memory_bytes: 29660
"""
n = int(sys.stdin.readline())
a, b = map(int, sys.stdin.readline().split())
c = list(map(int, sys.stdin.readline().split()))
s = [list(map(int,list(sys.stdin.readline()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

a = 100
b = 0.987654321
print('{0:06d}-{1:6f}'.format(a,b))  # 0埋め, 小数点出力桁指定時のときの出力
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]
"""

import math
import sys
import itertools
import queue
from fractions import gcd

def lcm(a, b):
    return a * b // gcd(a, b)


mod = 1000000007

if __name__ == "__main__":
    N, M, C = map(int, sys.stdin.readline().split())
    B = list(map(int, sys.stdin.readline().split()))
    correct = 0
    for _ in range(N):
        total = C
        for a, b in zip(list(map(int, sys.stdin.readline().split())), B):
            total += (a * b)
        if total > 0:
            correct += 1
    print(correct)



Measured memory_bytes: 5076
#include <bits/stdc++.h>
using namespace std;
#define SELECTER(_1, _2, _3, SELECT, ...) SELECT
#define REP1(i, n) for(int (i)=0; (i)<(n); (i)++)
#define REP2(i, a, b) for(int (i)=(a); (i)<(b); (i)++)
#define REP(...) SELECTER(__VA_ARGS__, REP2, REP1,) (__VA_ARGS__)
#define MOD 1000000007

template <class T> ostream& operator<<(ostream& os, const vector<T>& v){ os << "{"; for(size_t i=0; i<v.size(); i++) os << v[i] << (i+1==v.size() ? "" : ", "); os << "}"; return os; }
template <class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p){ return os << "{" << p.first << ", " << p.second << "}"; }

// 1-indexed
template <class X>
class FenwickTree {
    int n;
    vector<X> a;
public:
    FenwickTree(int n) : n(n), a(n+1, 0) {}
    X get(int i) {
        X sm = 0;
        for(; i > 0; i -= i&-i) sm += a[i];
        return sm;
    }
    void add(int i, X x) {
        for(; i <= n; i += i&-i) a[i] += x;
    }
    X at(int i){return get(i) - get(i-1);}
};

int main(){
    long long N, D, A;
    cin >> N >> D >> A;
    vector<pair<long long, long long>> XH(N);
    REP(i, N) cin >> XH[i].first >> XH[i].second;
    sort(XH.begin(), XH.end());

    vector<int> R(N);
    int head = 0;
    REP(tail, N){
        int x0 = XH[tail].first;
        while(true){
            if(head == N-1) break;
            if(XH[head+1].first > x0+2*D) break;
            head++;
        }
        R[tail] = head;
    }

    long long ans = 0;
    FenwickTree<long long> ft(N);
    REP(from, N){
        int to = R[from];
        long long rem = XH[from].second - ft.get(from+1);
        if(rem <= 0) continue;
        long long cnt = (rem+A-1)/A;
        ans += cnt;
        ft.add(from+1, A*cnt);
        ft.add(to+2, -A*cnt);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 5760
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
	    	Scanner sc = new Scanner(System.in);
	    	String s = sc.next();
	    	long count = 0;
	    	int dis = 0;
	    	for (int i = 0; i < s.length(); i++) {
			if (String.valueOf(s.charAt(i)).equals("W")) {
				count += (i - dis);
				dis++;
			}
		}
	    	System.out.println(count);
	}
}


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

int main() {
    int N, K;
    cin >> N >> K;
    int l[50];
    for (int i = 0; i < N; ++i) cin >> l[i];

    sort(l, l + N, greater<int>());  // a[0:N] を大きい順にソート
    int max = 0;
    for (int i = 0; i < K; ++i){
        max += l[i];
    }
    cout << max << endl;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7

cumsum = [A[0]]
for i in range(1,N):
  cumsum.append(A[i]+cumsum[i-1])

ans = 0
for i in range(N):
  ans += (A[i]*(cumsum[-1]-cumsum[i]))%MOD
  ans %= MOD

print(ans)

Measured memory_bytes: 107124
import sys
import os


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

    N, L = list(map(int, sys.stdin.readline().split()))
    S = sorted([line.rstrip() for line in sys.stdin.readlines()])
    print(*S, sep="")


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rep3(i, l, n) for (int i = l; i < n; ++i)
#define chmax(a, b) a = (a >= b ? a : b)
#define chmin(a, b) a = (a <= b ? a : b)
#define out(a) cout << a << endl
#define outa(a, n) rep(_, n) cout << a[_] << " "; cout << endl
#define SZ(v) (int)v.size()
#define inf (int)(1e9+7)
#define abs(x) (x >= 0 ? x : -(x))

int ans = 0;

void bfs() {
    int h, w;
    cin >> h >> w;
    char c[h][h];
    fill_n(*c, h * h, 0);
    int a[w], b[w];
    rep(i, w) {
        cin >> a[i] >> b[i];
        c[a[i] - 1][b[i] - 1] = 1;
        c[b[i] - 1][a[i] - 1] = 1;
    }
    rep(i, w) { // どの辺落とすか
        c[a[i] - 1][b[i] - 1] = 0;
        c[b[i] - 1][a[i] - 1] = 0;
        queue<int> q;
        q.push(0);
        int table[h];
        fill_n(table, h, 0);
        table[0] = 1;
        while (!q.empty()) {
            int y = q.front();
            q.pop();
            rep3(i, 1, h) {
                if (c[y][i] == 0) continue;
                if (table[i] == 1) continue;
                q.push(i);
                table[i] = 1;
            }
        }
        rep(i, h) if (table[i] == 0) { ans++; break; }
        c[a[i] - 1][b[i] - 1] = 1;
        c[b[i] - 1][a[i] - 1] = 1;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    bfs();
    out(ans);
}


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

int main(){
    int n;
    cin>>n;
    ll a[n];
    ll ans=1;
    int zero=0;
    rep(i,n){
        cin>>a[i];
        if(a[i]==0) zero++;
    }
    if(zero>0){
        cout<<0<<endl;
        return 0;
    }
    rep(i,n){
        if(a[i]<=1000000000000000000/ans){
            ans = ans*a[i];
        }else{
            cout<<-1<<endl;
            return 0;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 4372
#define _USE_MATH_DEFINES

#include<math.h>
#include<stdio.h>
#include<utility>
#include<algorithm>

int main() {
	int n, m, l, o, D;
	D = 0;
	m = 1;
	scanf("%d", &n);//////////////////////////
	while (m <= n) {
		if (m % 3 == 0) {
			printf(" %d", m);
		}
		else {
			l = m;
			while (l != 0) {
				o = l % 10;
				if (o == 3) {
					printf(" %d", m);
					break;
				}
				l /= 10;
			}
		}
		m++;
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 2736
w, h, n = map(int, input().split())
p, q, r, s = 0, 0, w, h
for i in range(n):
   x, y, a = map(int, input().split())

   if (a == 1):
      if (x > p):
         p = x
   elif (a == 2):
      if (x < r):
         r = x
   elif (a == 3):
      if (y > q):
         q = y
   else:
      if (y < s):
         s = y

if (r < p or s < q):
   print(0)
else:
   print((r - p)* (s - q))
          

Measured memory_bytes: 3064
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		double[] ary = new double[n];
		for(int i = 0; i < n; i++){
			ary[i] = sc.nextDouble();
		}
		Arrays.sort(ary);
		double ans = ary[0];
		for(int i = 1; i < n; i++){
			ans = (ans + ary[i]) / 2;
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 23252
using System;
using System.Collections.Generic;

class Program {
  static void Main() {
    var d = new Dictionary<char, char[]>();
    d['A'] = new char[] { 'X', 'Y' };
    d['X'] = new char[] { '-', 'Z' };
    d['Y'] = new char[] { 'X', '-' };
    d['Z'] = new char[] { 'W', 'B' };
    d['W'] = new char[] { 'B', 'Y' };
    d['B'] = new char[] { 'Y', 'X' };
    var p = "";
    while ((p = Console.ReadLine()) != "#") {
      char a = 'A';
      foreach (var c in p) {
        if (c == '0') a = d[a][0];
        else  a = d[a][1];
        if (a == '-') break;
      }
      Console.WriteLine(a == 'B' ? "Yes" : "No");
    }
  }
}


Measured memory_bytes: 17944
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    def parent(i):
        return i//2

    def left(i):
        return 2*i

    def right(i):
        return 2*i+1

    H = int(input())

    # 1オリジンにするために、0番目にNoneを入れておく
    A = [None] + list(map(int, input().split()))

    # 1オリジンでfor文回す
    for i in range(1, H+1):
        print('node ' + str(i) + ': ', end='')
        print('key = ' + str(A[i]) + ', ', end='')
        if 1 <= parent(i):
            print('parent key = ' + str(A[parent(i)]) + ', ', end='')
        if left(i) <= H:
            print('left key = ' + str(A[left(i)]) + ', ', end='')
        if right(i) <= H:
            print('right key = ' + str(A[right(i)]) + ', ', end='')
        print('')  # 改行のため



Measured memory_bytes: 5724
import sys
from collections import defaultdict, deque, Counter
#from bisect import bisect_left
#import heapq
#import math
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

n = int(stdin.readline().rstrip())
a = list(map(int, stdin.readline().rstrip().split()))
#A, B, C = map(int, stdin.readline().rstrip().split())
#S = [list(stdin.buffer.readline().decode().rstrip()) for _ in range(h)]

check = set(a)
coll = Counter(a)

if check == {0}:
    print("Yes")
elif len(check) == 3:
    if list(check)[0] ^ list(check)[1] ^ list(check)[2] == 0:
        if coll[list(check)[0]] == coll[list(check)[1]] == coll[list(check)[2]]:
            print("Yes")
        else:
            print("No")
    else:
        print("No")
elif len(list(check)) == 2:
    if list(check)[0] == 0:
        if coll[list(check)[0]] * 3 == n:
            print("Yes")
        else:
            print("No")
    elif list(check)[1] == 0:
        if coll[list(check)[0]] * 3 == n:
            print("Yes")
        else:
            print("No")
    else:
        print("No")
else:
    print("No")


Measured memory_bytes: 14504
#include <bits/stdc++.h>
using namespace std;
  #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define int long long
  #define endl "\n"
  const int N = 200005;

int32_t main()
{



    IOS

    


    int x;
    cin >> x;

    vector<pair<int,int>> v;

    for(int i = -5000; i<= 5000; i++)
    {
      int x = i*i*i*i*i;
      //cout << i*i*i*i*i << endl;
      v.push_back(make_pair(x,i));
    }

    sort(v.begin(),v.end());

    for(int i = 0; i < v.size(); i++)
    {
      for(int j = i +1; j < v.size(); j++)
      {
        if(v[j].first-v[i].first == x)
        {
          cout <<  v[j].second << " " << v[i].second;
          return 0;
        }
      }
    }







    
    return 0;
}



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

// C++ program to find if a number is divisible by 
// 9 or not 
#include<bits/stdc++.h> 
using namespace std; 
  
// Function to find that number divisible by 9 or not 
int check(string str) 
{ 
    // Compute sum of digits 
    int n = str.length(); 
    int digitSum = 0; 
    for (int i=0; i<n; i++) 
        digitSum += (str[i]-'0'); 
  
    // Check if sum of digits is divisible by 9. 
    return (digitSum % 9 == 0); 
} 
  
int main(){
string str;
cin>>str;
if(check(str)){
	cout<<"Yes"<<endl;
}
else
cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 3920
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = 0
temp = 21
for i in range(N):
    ans+=B[A[i]-1]
    if A[i]-temp == 1:
        ans+=C[temp-1]
    temp = A[i]
print(ans)

Measured memory_bytes: 3064
#######################################
import numpy as np
#######################################
n = int(input())
a = np.array(list(map(int, input().split())))
ret = np.zeros(n+1, dtype="int")
tmp = list(range(n+1))
ret2 = []

for i in reversed(list(range(n))): 
  if sum(ret[::i+1][1:])%2 != a[i]:
    ret[i+1] = 1
    ret2.append(i+1)

print(sum(ret[1:]))
ret2 = sorted(ret2)
print(" ".join(list(map(str, ret2))))

Measured memory_bytes: 35840
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n; cin >> n;
  V<> a(n); for (auto&& e : a) cin >> e;
  V<> idx(n);
  iota(begin(idx), end(idx), 0);
  sort(begin(idx), end(idx), [&](int i, int j) { return a[i] < a[j]; });
  for (int i = 0; i < n; ++i) {
    cout << idx[i] + 1 << " \n"[i == n - 1];
  }
}

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

using namespace std;

#define RPT(n) for (int i = 0; i < n; i++)

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

    int max = 0;
    int cur = 0;

    RPT(N)
    {
        if (S[i] == 'I')
        {
            cur++;
            if (cur > max)
                max = cur;
        }
        else
            cur--;
    }

    cout << max << endl;

    return 0;
}


Measured memory_bytes: 256
/* 
   AOJ 1126
   The Secret Number

*/

#include<stdio.h>
#define WH_MAX 80
typedef struct coded_number
{
  int len;
  char s[WH_MAX + WH_MAX];
}coded_number;

int w, h;
char f[WH_MAX][WH_MAX];
coded_number memo[WH_MAX][WH_MAX];

void copy(coded_number *src, coded_number *dst)
{
  int i;
  dst->len = src->len;
  for(i = 0; i <= src->len; i++)
    dst->s[i] = src->s[i];

}

int ok(int x, int y)
{
  return (0 <= x && x < w && 0 <= y && y < h && '0' <= f[y][x] && f[y][x] <= '9');
}

void init(coded_number* x)
{
  x->len = 0;
  x->s[0] = '\0';
}

int is_zero(coded_number *x)
{
  int i;
  if(!(x->len > 0))
    return 0;
  else
    for(i = 0; i < x->len && x->s[i] == '0'; i++);
  return i == x->len;
}

int comp(coded_number *x, coded_number *y)
{
  int i, x_len = x->len, y_len = y->len;
  if(x_len > y_len)
    return -1;
  else if(x_len < y_len)
    return 1;
  else
    for(i = 0; i < x_len; i++)
      {
	if(x->s[i] > y->s[i])
	  return -1;
	else if(x->s[i] < y->s[i])
	  return 1;
      }
  return 0;
}


void add_char(coded_number* dst, char c)
{
  int i, j;
  for(i = dst->len, j = dst->len + 1; i >= 0; i--, j--)
    dst->s[j] = dst->s[i];
  dst->s[0] = c;
  dst->len++;
}

coded_number* search(int x, int y)
{
  coded_number right, below, ret;
  int comp_ret;
  init(&ret);
  if(memo[y][x].len > 0)
    return &memo[y][x];

  else if(ok(x, y))
    {
      copy(search(x + 1, y), &right);
      copy(search(x, y + 1), &below);
      if(comp(&right, &below) < 0)
	copy(&right, &ret);
      else
	copy(&below, &ret);
      add_char(&ret, f[y][x]);
      copy(&ret, &memo[y][x]);
      return &memo[y][x];
   }
  return &ret;
}

int main(void)
{
  int i, j;
  coded_number ret;


  while(scanf("%d %d", &w, &h), (w && h))
    {

      for(i = 0; i < h; i++)
	scanf("%s", f[i]);

      for(i = 0; i < WH_MAX; i++)
	for(j = 0; j < WH_MAX; j++)
	  init(&memo[i][j]);
      init(&ret);

      for(i = 0; i < h; i++)
	for(j = 0; j < w; j++)
	  if('0' < f[i][j] && f[i][j] <= '9')
	    search(j, i);


      for(i = 0; i < h; i++)
	for(j = 0; j < w; j++)
	  if(comp(&ret, &memo[i][j]) > 0)
	    copy(&memo[i][j], &ret);

      printf("%s\n", ret.s);
    }
  return 0;
}

Measured memory_bytes: 1656
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
//ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

#define MAX_V 1000000

int main(){
	cin.tie(0);
		ios::sync_with_stdio(false);
		int N;
		cin >> N;
		vector<int> A(N), B(N), C(N);
		rep(i, 0, N) cin >> A[i];
		rep(i, 0, N) cin >> B[i];
		rep(i, 0, N) cin >> C[i];

		ll rsl = 0;
		vsort(A);
		vsort(C);
		rep(i, 0, N) {
			ll tmp1, tmp2;
			tmp1 = lower_bound(A.begin(), A.end(), B[i]) - A.begin();
			tmp2 = C.end() - upper_bound(C.begin(), C.end(), B[i]);
			rsl += (tmp1 * tmp2);
		}

		cout << rsl << endl;
}


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

int main(){
    string S, T;
    cin >> S >> T;
    int n = S.size(), m = T.size();
    vector<vector<int>> D(2 * n + 1, vector<int>(26, n + 1));
    string U = S + S;

    for (int i = 2 * n; i > 0; i--){
        for (int j = 0; j < 26; j++)
            D[i - 1][j] = D[i][j] + 1;
        int k = U[i - 1] - 'a';
        D[i - 1][k] = 1;
    }

    int64_t ans = 0;
    int64_t cur = -1;
    for (int i = 0; i < m; i++){
        int k = T[i] - 'a';
        if (D[cur + 1][k] > n){
            puts("-1");
            return 0;
        }
        cur += D[cur + 1][k];
        if (cur >= n){
            ans++;
            cur -=n;
        }
    }

    cout << ans * n + cur + 1 << endl;
}

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

// NOTE TO SELF // try to simplyfy the problem

#define rep(i,a,n) for (int i = a; i <= n; i++)

#define ll long long int

//const int mod=1000000007;
using namespace std;
 
/*int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[] = {0, 1, 0, -1, 1, -1, -1, 1};
*/


ll dp[100005][3];


int main()
{


    ll n;
    cin>>n;
    
    dp[0][0]=0;
    dp[0][1]=0;
    dp[0][2]=0;
    
    ll flag=1;
    
    ll k=n;
    
    while(k--)
    {
        ll a,b,c;
        cin>>a>>b>>c;
        
        dp[flag][0]= a + max(dp[flag-1][1],dp[flag-1][2]);
        dp[flag][1]= b + max(dp[flag-1][2],dp[flag-1][0]);
        dp[flag][2]= c + max(dp[flag-1][1],dp[flag-1][0]);
        
        
        flag++;
        
    }
    
    cout<< max(dp[n][0],max(dp[n][1],dp[n][2]))<<endl;
    
    
}


Measured memory_bytes: 5940
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  vector<int> v;
  int a,sum;
  sum=0;
  cin>>a;
  for(int i=0;i<a;i++){
    int tmp;
    cin>>tmp;
    v.push_back(tmp);
  }
  for(int i=0;i<a;i++){
    for(int j=i+1;j<a;j++){
      sum+=v[i]*v[j];
    }
  }
  cout<<sum<<endl;
}




Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<math.h>

typedef struct{
	int color;
	int number;
}Kind;

Kind U[1000000];

int main(){
	int i,j,a,c,b;
	
	while(~scanf("%d",&a)){
		if(a==0)break;
		
		memset(U,0,sizeof(U));
		b=a;
		for(i=0;i<a;i++){
			scanf("%d",&c);
			for(j=0;j<b;j++){
				if(U[j].color==c || U[j].color==0){
					U[j].color=U[j].color>0?U[j].color:c;
					++U[j].number;
					break;
				}
			}
			b=j+1;
		}
		
		j=-1;
		for(i=0;i<a;i++){
			if(2*U[i].number>a){
				j=i;
				break;
			}
		}
		
		if(j==-1){
			printf("NO COLOR\n");
		}else{
			printf("%d\n",U[j].color);
		}
	}
	return 0;
}

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

using namespace std;

int main()
{
   int a,b,c;
   cin >>a>>b>>c;
   int count = 0;
   for(int i = a;i<=b;i++){
       if(c % i == 0){
           count++;
       }
   }
   cout << count << endl;
    return 0;
}


Measured memory_bytes: 3112
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
#define INF 100000000
#define MAXN 100010
#define INT_MAX 2147483647
typedef long long ll;

int n, q;
int dat[MAXN * 4];

// 初期化
void init(int n_) {
    n = 1;
    while (n < n_) n *= 2;
    for (int i = 0; i < 2 * n - 1; i++) dat[i] = INT_MAX;
}

// k番目の値をxに変更
void update(int k, int x) {
    k += n-1;
    dat[k] = x;
    while (k > 0) {
        k = (k-1) / 2;
        dat[k] = min(dat[k*2+1], dat[k*2+2]);
    }
}

// [a, b)の最小値を求める
int query(int a, int b, int k, int l, int r) {
    if (a >= r || b <= l) return INT_MAX;
    if (a <= l && r <= b) return dat[k];
    int vl = query(a, b, 2*k+1, l, (l+r)/2);
    int vr = query(a, b, 2*k+2, (l+r)/2, r);
    return min(vl, vr);
}

int main(void) {
    cin >> n >> q;
    init(n);
    for (int i = 0; i < q; i++) {
        int com, x, y;
        cin >> com >> x >> y;
        if (com == 0) {
            update(x, y);
        } else {
            cout << query(x, y+1, 0, 0, n) << endl;
        }
//        for (int i = 0; i < 2*n-1; i++) {
//            cout << dat[i] << endl;
//        }
    }
    return 0;
}

Measured memory_bytes: 2192
#include <bits/stdc++.h>
#define int long long int
#define mod(x) ((x % MOD) + MOD) % MOD
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define RFORE(i,a,b) for(int i=(b);i>=(a);--i)
#define REP(i,n) FOR(i,0,n)
#define ALL(c) (c).begin(),(c).end()
#define RALL(c) (c).rbegin(),(c).rend()
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define SZ(c) (int)((c).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define LB(c,x) (int)(lower_bound(ALL(c),x)-(c).begin())
#define UB(c,x) (int)(upper_bound(ALL(c),x)-(c).begin())
#define COUNT(c,x) (UB(c,x)-LB(c,x))
#define UNIQUE(c) SORT(c); (c).erase(unique(ALL(c)),(c).end());
#define COPY(c1,c2) copy(ALL(c1),(c2).begin())
#define EXIST(s,e) (bool)((s).find(e)!=(s).end())
#define PB push_back
#define MP make_pair
#define DEL(v) decltype(v)().swap(v)
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
using namespace std;
template<typename T1, typename T2> using P = pair<T1,T2>;
template<typename T> using V = vector<T>;
struct edge { int from, to; int cost; };
bool operator< (const edge &edge1, const edge &edge2) { return edge1.cost < edge2.cost; };
const int INF = 1e18;
const int MOD = 1e9+7;

template<typename T> ostream& operator << (ostream& s, const V<T>& v) {
   s << "[";
   for (int i = 0; i < v.size(); i++) { s << v[i]; if (i < v.size() - 1) s << " "; }
   s << "]";
   return s;
}

signed main()
{
   int N, K; cin >> N >> K;
   cout << ((N+1)/2 >= K ? "YES" : "NO") << endl;
   return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#define MOD 1000000007
#define mkp make_pair
typedef long long ll;
using namespace std;

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

  vector<int> ans(N+1,0);
  for(int i=N;i>=1;i--){
    int now=i;
    int res=0;
    for(int j=2;i*j<=N;j++){
      res=res+ans[i*j];
      res%=2;
    }
    if(res==A[i]) ans[i]=0;
    else ans[i]=1;
  }

  vector<int> las;
  for(int i=1;i<=N;i++){
    if(ans[i]) las.push_back(i);
  }

  cout<<las.size()<<endl;
  for(int i=0;i<las.size();i++) cout<<las[i]<<" ";
  cout<<endl;


  return 0;
}


Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define REP(i, n) for(int i = 1; i < (int)(n); ++i)
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> ans(N, 0);
    rep(i, M) {
        int a, b;
        cin >> a >> b;
        ++ans[a - 1];
        ++ans[b - 1];
    }
    rep(i, N) {
        cout << ans[i] << endl;
    }
    return 0;
}


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

int main(){
    int N,D,i,j,k;
    cin >> N >> D;
    vector< vector<int> > x (N, vector<int>(D) );
    for (i = 0; i<N; ++i){
        for (j =0; j<D; ++j){
            cin >> x[i][j];
        }
    }
    int cnt = 0;
    for (i=0; i<N; ++i){
        for (j=i+1; j<N; ++j){
            int temp = 0;
            for (k=0; k<D; ++k){
                temp += pow(x[i][k]-x[j][k],2);
            }
            double res = 0;
            res = sqrt(temp);
            if (fmod(res,1.0) == 0){
                cnt+=1;
            }
        }
    }
    cout << cnt << endl;
    /*
    for (i = 0; i<N; ++i){
        for (j =0; j<D; ++j){
            cout <<  x[i][j];
        }
        cout << endl;
    }
    */
    return 0;
}


Measured memory_bytes: 256
N = int(input())
a = []
for i in range(N):
    a.append(int(input()))
# ここまでが入力

b = [0 for _ in range(N)]   # 要素b[n]には、ボタンb[n]を押したことがあれば 1 なければ 0 が格納
c = 1   # ついているボタンの数を格納する変数
counter = 0     # 押したボタンの回数

while c != 2:
    if b[c-1] == 1:      # ボタンｃが押されたことがある場合
        counter = -1
        break
    b[c-1] = 1      # リストbにボタンｃが押されたことを記録させる
    c = a[c-1]      # ボタンを押して次のボタンが光る
    counter += 1

print(counter)

Measured memory_bytes: 7852
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,k,cc[500000],dd[500000],a,b;
char s[500000];
int main(){
	scanf("%d%d%d",&n,&a,&b);
	printf("%d\n",min(n*a,b));
	return 0;
} 

Measured memory_bytes: 2304
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int [] ways = new int[200001];
        ArrayList<Integer> stones = new ArrayList<>();

        int current = sc.nextInt();
        stones.add(current);
        for(int i = 1; i < n; i++){
            current = sc.nextInt();
            if (current != stones.get(stones.size()-1)){
                stones.add(current);
            }


        }
        int [] count = new int[stones.size()];
        count[0] = 1;
        ways[stones.get(0)] = 1;
        for (int i = 1; i < stones.size();i++){
            count[i] = (count[i - 1] + ways[stones.get(i)]) % 1_000_000_007;
            ways[stones.get(i)] = count[i];
        }

        System.out.println(count[stones.size() - 1]);
    }
}


Measured memory_bytes: 96688
//xtwakioi! xtwddYnoi(双重含义)!
#include <bits/stdc++.h>
#define ri register
#define int long long
#define E (n+1)
using namespace std; const int N=1000100, Mod=1e9+7;
inline int read()
{
    int s=0, w=1; ri char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48), ch=getchar();
    return s*w;
}
int n,g[N][2];
signed main()
{
    n=read();
    int res=0;
    for(ri int i=1;i<=n;i++) g[i][0]=read(), g[i][1]=read();
    for(ri int s=0;s<(1ll<<2);s++)
    {
        int mx=-1e18, mi=1e18;
        for(ri int i=1;i<=n;i++)
        {
            int qwq=0;
            for(ri int j=0;j<2;j++)
            {
                qwq+=(s&(1ll<<j))?g[i][j]:-g[i][j];
            }
            mx=max(mx,qwq), mi=min(mi,qwq);
        }
        res=max(res,mx-mi);
    }
    printf("%lld\n",res);
    return 0;
}

Measured memory_bytes: 6900
#ifdef _MSC_VER
#include <__msvc_all_public_headers.hpp>
#undef min
#undef max
#else
#define NDEBUG
#include <bits/stdc++.h>
#endif

using namespace std;
using large = long long;

int main() {
    int n, k; // 100'000;
    cin >> n >> k;

    auto toss = vector<double>(n);
    for (auto t = 0; t < n; ++t) {
        auto first = t + 1;
        if (first >= k) {
            toss[t] = 0;
            continue;
        }
        auto wins = 0;
        for (auto score = first; score < k; score *= 2)
            wins++;
        toss[t] = wins;
    }

    auto sum = 0.0;
    for (auto t : toss) {
        if (t == 0) {
            sum += 1.0;
            continue;
        }
        sum += pow(0.5, double(t));
    }

    cout << setprecision(15) << (sum / n) << endl;
    return 0;
}


Measured memory_bytes: 4140