akhauriyash/Code-Regression huggingface dataset:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {

		String strLine ="";
		BufferedReader stdReader =
				new BufferedReader(new InputStreamReader(System.in));

		int MAX_DETASET  = 100;
		int cnt = 0;

		boolean nullflug = true;
		ArrayList<Integer> lineList1 = new ArrayList<Integer>();
		ArrayList<Integer> lineList2 = new ArrayList<Integer>();
		ArrayList<Integer>	numberList = new ArrayList<Integer>();
		ArrayList<Integer> tateyokoList = new ArrayList<Integer>();

		int lineMaxTate = 100;
		int lineMaxYoko = 100;

		//1. int?????????????????\???????????????????????????

		while((strLine = stdReader.readLine()) != null) {

			String[] temp = strLine.split(",",0);

			if(cnt > lineMaxYoko){
				break;
			}else if(temp.length > 1 ){//????????????????????????
				lineList1.add(Integer.parseInt(temp[0])-1);
				lineList2.add(Integer.parseInt(temp[1])-1);

			}else{

				if(cnt == 0){
					lineMaxTate = Integer.parseInt(temp[0]);
				}else if(cnt == 1){
					lineMaxYoko = Integer.parseInt(temp[0]);

				}
				cnt++;
			}

		}





		//2. ???????????????????????¨??????????????\??£?????????????????????????????§???????????????
		//   ????§??????????numberList???????´?

		for(int j = 0; j< lineMaxTate; j++){

			int now = j;

			for(int i = lineMaxYoko - 1; i >=0 ; i--){

				if(lineList1.get(i) == now){

					now = lineList2.get(i);

				}else if (lineList2.get(i) == now){

					now = lineList1.get(i);

				}else{ //????????????

				}

			}

			numberList.add(now);
		}


		//3. ??????

		for(int i = 0; i < numberList.size(); i++){

			System.out.println(numberList.get(i)+1);

		}


	}


}

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

#define rep(ver,n) rep2(ver,0,n)
#define rep2(ver,m,n) for(int ver=m;ver<(n);ver++)
#define loop while(true)
#define dup(x,y) (((x)+(y)-1)/(y))
#define all(v) (v).begin(), (v).end()
#define debug(x) std::cerr<<#x<<": "<<x<<"\n"
#define debug2(x,y) std::cerr<<#x<<": "<<x<<", "<<#y<<": "<<y<<"\n"
#define debug3(x,y,z) std::cerr<<#x<<": "<<x<<", "<<#y<<": "<<y<<", "<<#z<<": "<<z<<"\n"

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

ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

int main(){
  ll a,b,c,d;
  cin>>a>>b>>c>>d;
  
  ll M=a*c;
  M=max(M,a*d);
  M=max(M,b*c);
  M=max(M,b*d);
  
  cout<<M;
  
  return 0;
}


Measured memory_bytes: 3620
A,B,C,D = map(int, input().split())

if C <= A:
    if D <= A:
        print(0)
    elif A < D <= B:
        print(D-A)
    else:
        print(B-A)
elif A < C <= B:
    if A < D <= B:
        print(D-C)
    else:
        print(B-C)
else:
    print(0)

Measured memory_bytes: 38256
#include<iostream>
#include<iomanip>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<string>
#include<utility>
#include<numeric>
#include<algorithm>
#include<cmath>
#include<climits>

//エイリアス
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

class Stream{
public:
    Stream(){

    }
    //配列以外の入力を受け取る
    void read(){

    }
    template<typename First, typename... Rest>
    void read(First& first, Rest&... rest){
        cin >> first;
        read(rest...);
    }
    template<typename T>
    vector<T> read_vec(size_t n){
        vector<T> tmp(n);
        for(size_t i = 0; i < n; i++){
            cin >> tmp[i];
        }
        return tmp;
    }
    //配列を区切って出力する
    template<typename T>
    void write_vec(vector<T>& v, char divider){
        for(size_t i = 0; i < v.size(); i++){
            cout << v[i] << divider;
        }
    }
};



int main(){
    Stream io;
    
    ll N;
    io.read(N);

    cout << N * (N - 1) / 2;

    return 0;
}


Measured memory_bytes: 3540
#include <algorithm>
#include <cmath>
#include <complex>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#include <functional>
#include <cstring>
#include <regex>
#include <random>
#include <cassert>
#include <stack>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, s, n) for (int i = (s); i < (int)(n); i++)
#define revrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define revrepr(i, s, n) for (int i = (n) - 1; i >= s; i--)
#define debug(x) cerr << #x << ": " << x << "\n"
#define popcnt(x) __builtin_popcount(x)

using ll = long long;
using P = pair<int, int>;

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

template<class T>
istream& operator >>(istream &is, vector<T> &v) {
    for (int i = 0; i < (int)v.size(); i++) cin >> v.at(i);
    return is;
}

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

template<class T>
void print(const vector<T> &v, const string &delimiter) { rep(i, v.size()) cout << (0 < i ? delimiter : "") << v.at(i); cout << endl; }

template<class T>
void print(const vector<vector<T>> &vv, const string &delimiter) { for (const auto &v: vv) print(v, delimiter); }

const double PI = acos(-1.0);

int main() {
    double r;
    cin >> r;
    printf("%.10lf\n", r * 2 * PI);
}

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

using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for(auto&& x:a)cin>>x;
  vector<int> b;
  for(auto&& x:a){
    auto it = upper_bound(b.begin(), b.end(), x, greater<int>());
    if(it == b.end()){
      b.emplace_back(x);
    }
    else{
      *it = x;
    }
  }
  cout << b.size() << endl;
}

Measured memory_bytes: 1276
// Half and Half
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;

int main() {
    int A, B, C, X, Y;
    cin >> A >> B >> C >> X >> Y;
    int money = 1 << 30;
    for (int i = 0; i <= 100000; i++) {
        money = min(money, i * 2 * C + max(0, X-i) * A + max(0, Y-i) * B);
    }
    cout << money << endl;
}

Measured memory_bytes: 256
from itertools import permutations

N = int(input())
P = [int(x) for x in input().split()]
Q = [int(x) for x in input().split()]

a, b = -1, -1
for i, p in enumerate(permutations(range(1, N + 1), N), 1):
    if list(p) == P:
        a = i
    if list(p) == Q:
        b = i
    if a >= 1 and b >= 1:
        break

print(abs(a - b))

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

int main(){
	string t,right,left;
	int m,i,num,count=0;

	while(1){
	cin>>t;
	if(t == "-") break;
	cin>>m;
	for(i=0;i<m;i++){
		cin>>num;
		count+=num;
	}

	right = t.substr(0, count % t.length());
	left = t.substr(count % t.length(), t.length());

	cout<<left<<right<<"\n";

	count = 0;
	}

	return 0;
}

Measured memory_bytes: 3148
using System;
using System.Linq;
using System.Collections.Generic;

class P
{
    static void Main()
    {
        Console.ReadLine();
        long[] ns = Console.ReadLine().Split().Select(long.Parse).OrderByDescending(x => x).ToArray();
        int count = 0;
        long res = 1;
        long last = 0;
        for (int i = 0; i < ns.Length; i++)
        {
            if (ns[i] == last)
            {
                res *= ns[i];
                count++;
                last = -1;
                if (count >= 2) break;
            }
            else
            {
                last = ns[i];
            }
        }
        if (count < 2)
        {
            Console.WriteLine(0);
        }
        else
        {
            Console.WriteLine(res);
        }
    }
}

Measured memory_bytes: 26080
s = input()
count = int(input())
li = ["print", "reverse", "replace"]
for i in range(count):
    exp= input().split()
    a = int(exp[1])
    b = int(exp[2])
    ind = li.index(exp[0])
    if ind == 0:
        print(s[int(a):int(b)+1])
    elif ind == 1:
        s = s[:a] + s[a:b+1][::-1] + s[b+1:]
    else:
        s = s[:a] + exp[3] + s[b+1:]

Measured memory_bytes: 7688
#include <iostream>

using namespace std;

int main() {
  int N;
  cin >> N;
  int max = 0, ans = 1;

  for (int i = 1; i <= N; i++) {
    int cnt = 0;
    int tmp = i;

    while (tmp != 0) {
      if (tmp % 2 == 0) {
        tmp /= 2;
        cnt++;
        continue;
      }
      tmp = 0;
    }

    if (max < cnt) {
      max = cnt;
      ans = i;
    }
  }

  cout << ans;
}

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

int main(){
  int N;
  cin >> N;
  vector<int> A(N), B(N);
  for(int i = 1; i < N; ++i) cin >> A[i], ++B[A[i]-1];
  for(auto e : B)
    cout << e << endl;
}


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

int main() {
	int n, table[10][10]={};
	cin>>n;
	
	for(int i=1;i<10;i++){
		for(int j=1;j<10;j++){
			table[i][j]=i*j;
		}
	}
	
	for(int i=1;i<10;i++){
		for(int j=1;j<10;j++){
		if(n==table[i][j]){
			cout<<"Yes";
			return 0;
			}
		}
	}
	
	cout<<"No";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
#include <vector>
#include <queue>
#include <iomanip>
#include <string>
#include <algorithm>
using namespace std;
using Graph = vector<vector<int>>;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep_1 (i,j,n) for(int i=j;i<n;i++)
typedef long long ll;
typedef long l;
const ll l_INF = 1010101010101010;
const int INF = 1010101010;
const int dx[4] = {-1,0,1,0};
const int dy[4] = {0,-1,0,1};
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int main(){
  int n,m,Q; cin>>n>>m>>Q;
  vvi x(n+1,vi(n+1));
  rep(i,m){
    int l,r; cin>>l>>r;
    x[l][r]++;
  }
  vvi c(n+1,vi(n+1));
  rep(i,n)rep(j,n) c[i+1][j+1]+=c[i+1][j]+x[i+1][j+1];
  rep(i,Q){
    int p,q; cin>>p>>q;
    int ans=0;
    for(int j=p;j<q+1;j++) ans+=c[j][q]-c[j][p-1];
    cout<<ans<<endl;
  }
}


Measured memory_bytes: 5596
#include <bits/stdc++.h>
#define io() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); srand(time(NULL));
 
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

signed main(){
    io();
    int n; cin >> n;
    vector<int> v(n), cpy;
    for(int i = 0; i < n; ++i){
        cin >> v[i];
    }
    cpy = v;
    sort(v.rbegin(), v.rend());
    for(int i = 0; i < n; ++i){
        if(cpy[i] == v[0]){
            cout << v[1] << '\n';
        }else{
            cout << v[0] << '\n';
        }
    }
    return 0; 
}

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

using i64 = long long;

struct Man {
	int a, b, c; };

const int N = 1e5 + 5;

multiset<i64> bag;
i64 ant;
int x, y, z, n;

Man p[N];
i64 sl[N], sr[N];

int main() {
#ifdef HOME
	freopen("agc18.in", "r", stdin);
	freopen("agc18.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	i64 sum;

	cin >> x >> y >> z;
	n = x + y + z;
	for (int i = 0; i < n; ++i)
		cin >> p[i].a >> p[i].b >> p[i].c;

	sort(p, p + n, [&](Man u, Man v) {
		return u.a - u.b > v.a - v.b; });

	sum = 0;
	for (int i = 0; i < x + z; ++i) {
		bag.insert(p[i].c - p[i].a);
		sum+= p[i].a;
		if ((i + 1) - x > 0) {
			auto it = bag.end(); --it;
			sum+= *it;
			bag.erase(it); }
		sl[i] = sum; }

	sum = 0;
	bag.clear();
	for (int i = n - 1; i >= x; --i) {
		bag.insert(p[i].c - p[i].b);
		sum+= p[i].b;
		if ((n - i) - y > 0) {
			auto it = bag.end(); --it;
			sum+= *it;
			bag.erase(it); }
		sr[i] = sum; }

	for (int i = x - 1; i < n - y; ++i)
		ant = max(ant, sl[i] + sr[i + 1]);

	cout << ant << endl;

	return 0; }


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

using namespace std;

const int MAXN = 5e1+2;

long long K;
long long a[MAXN] = {0};
int N;

void solve(){
	cin>>K;
	if (K==0){
		cout<<2<<endl;
		cout<<"0 1"<<endl;
		return;
	}
	if (K==1){
		cout<<2<<endl;
		cout<<"0 2"<<endl;
		return;
	}
	if (K<=100){
		N = 2;
	}
	else{
		N = 50;
	}
	for (int i=0;i<N;i++){
		a[i] = i;
	}
	long long rnd = K/N;
	for (int i=0;i<N;i++){
		a[i] += rnd;
	}
	long long res = K - N*rnd;
//	cout<<"res "<<res<<endl;
	for (int i=0;i<res;i++){
		a[N-1-i] += 1;
	}
	cout<<N<<endl;
	for (int i=0;i<N;i++){
		cout<<a[i]<<' ';
	}
	cout<<endl;
}

int main(){
// 	freopen("in.txt","r",stdin);
// 	freopen("out.txt","w",stdout);
	std::ios::sync_with_stdio(false);

//	int TestCase;
//	cin>>TestCase;
//	for (int i=0;i<TestCase;i++){
		solve();
//	}

	return 0;
}



Measured memory_bytes: 256
#include "iostream"
#include "vector"
#include "array"
#include "string"
#include "algorithm"
#include<queue>

using namespace std;
#define rep(p,q) for(int i = p;i < q;i++)

//4

int main(void) {
	int n = 0;
	cin >> n;
	vector<long int> a = vector<long int>();
	rep(0, n) {
		long int ax = 0;
		cin >> ax;
		a.push_back(ax);
	}
	sort(a.begin(), a.end());
	long int left = a[a.size() - 1];
	long int right = 10000000000;
	int half = left / 2 + left % 2;
	rep(0, n) {
		if (abs(half - a[i]) < abs(half - right)) {
			right = a[i];
		}
		else break;
	}
	cout << left << " " << right << endl;
}

Measured memory_bytes: 1400
import java.util.Scanner;

    class Main {
        public static void main (String[] args) throws java.lang.Exception {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt(), q = sc.nextInt();
            Solution sol = new Solution();

            Node root = sol.buildTree(0, n - 1);

            for(int i = 0; i < q; i++) {
                int c = sc.nextInt(), x = sc.nextInt(), y = sc.nextInt();
                if(c == 0) sol.update(root, y, x);
                else System.out.println(sol.query(x, y, root));
            }
        }
    }
    class Node{
        int start;
        int end;
        int min;
        Node left;
        Node right;
        Node(int s, int e){
            start = s;
            end = e;
            min = Integer.MAX_VALUE;
        }
    }

    class Solution{
        public Node buildTree(int start, int end){
            if(start == end){
                return new Node(start, end);
            }

            int mid = (start + end)/2;

            Node left = buildTree(start, mid);
            Node right = buildTree(mid + 1, end);

            Node root = new Node(start, end);
            root.left = left;
            root.right = right;
            return root;
        }

        public void update(Node root, int val, int index){
            if(root.start == index && root.end == index){
                root.min = val;
                return;
            }

            int mid = root.start + (root.end - root.start)/2;

            if(index <= mid){
                update(root.left, val, index);
            }else{
                update(root.right, val, index);
            }

            root.min = Math.min(root.left.min, root.right.min);
        }

        public int query(int start, int end, Node root){
            if(root.start > end || root.end < start ) return Integer.MAX_VALUE;
            if(root.start == start && root.end == end){
                return root.min;
            }

            int mid = root.start + (root.end - root.start)/2;

            if(end <= mid){
                return query(start, end, root.left);
            }else if(start > mid){
                return query(start, end, root.right);
            }else{
                int left = query(start, mid, root.left);
                int right = query(mid + 1, end, root.right);
                return Math.min(left, right);
            }

        }
    }




Measured memory_bytes: 116900
#include<iostream> 
#include<vector> 
#include<algorithm> 

using namespace std;

int main()
{
	int n;
	cin >> n;
	
	vector<int> a(3);
	for(int i=0;i<3;i++)
		cin >> a[i];
	sort(a.begin(),a.end());
	vector<int> l(n);
	for(int i=0;i<n;i++)
		cin >> l[i];
	sort(l.begin(),l.end());
	
	//全探索

	long long ans=10000000000008;

	for(int i=0;i<=n-3;i++)
	{
		for(int j=1;j<=n-i-2;j++)
		{
			for(int k=1;k<=n-i-j-1;k++)
			{

				int m=n-i-j-k;
				
					vector<int> per(n);
					for(int p=0;p<n;p++)per[p]=p;
					do
					{
						long long tmp;
						tmp=10*(j-1)+10*(k-1)+10*(m-1);
						long long tmpa=0;
						long long tmpb=0;
						long long tmpc=0;
						for(int ii=1;ii<=n-i;ii++)
						{	
							if(ii<=j)
								tmpa+=l[per[ii-1]];
							else if(ii<=j+k)
								tmpb+=l[per[ii-1]];
							else
								tmpc+=l[per[ii-1]];
						}

						tmp+=abs(tmpa-a[0])+abs(tmpb-a[1])+abs(tmpc-a[2]);
						ans=min(ans,tmp);	
					}
					while(next_permutation(per.begin(),per.end()));
			}
		}
	}


	cout << ans << endl;

}




Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <map>
#include <string.h>
#include <math.h>
#include <set>
#include <vector>
#include <algorithm>
#define rep(i, n) for(int i = 0; i < n; i++)
#define All(a) (a).begin(), (a).end()
using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    vector<pair<long, long>> a(n);
    rep(i, n) cin >> a[i].first >> a[i].second;
    sort(a.begin(), a.end());
    long ans = 0;
    int index = 0;
    while(index < n){
        if(m >= a[index].second){
            m -= a[index].second;
            ans += a[index].first * a[index].second;
            index++;
        }
        else break;
    }
    ans +=  m * a[index].first;
    cout << ans << endl;
}


Measured memory_bytes: 1792
#include <iostream>

int main() {
  int n; std::cin >> n;
  long long sum = ((1LL + n) * n) / 2;
  int c3 = n / 3;
  int c5 = n / 5;
  int c15 = n / 15;
  sum -= (((1LL + c3) * c3) / 2 * 3);
  sum -= (((1LL + c5) * c5) / 2 * 5);
  sum += (((1LL + c15) * c15) / 2 * 15);
  std::cout << sum << std::endl;
  
  return 0;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define ll long long 
#define ret return
#define PB push_back
#define lc 2 * v
#define rc 2 * v + 1
#define mid (s + e) / 2
#define pll pair <long long ,  long long>
#define FAST ios::sync_with_stdio(false);cin.tie(0);

const int maxn = 2e5 + 10 , INF = 1e9 + 10;
int a[maxn] , color[maxn] , n;

bool check(int k) {
    fill(color , color + maxn , 0); 
    for (int i = 1; i <= 2 * n - 1; ++i) {
        if(a[i] >= k) {
            color[i] = 1;
        }
        else {
            color[i] = 0;
        }
    }
    if((color[n] == color[n - 1]) || (color[n] == color[n + 1])) {
        return color[n];
    }
    ll dis1 = INF , dis2 = INF , c1 = -1 , c2 = -1;
    for (int i = n - 1; i >= 1; --i) {
        if(color[i] == color[i + 1]) {
            dis1 = n - i;
            c1 = color[i];
            break;
        }
    }
    for (int i = n + 1; i <= 2 * n - 1; ++i) {
        if(color[i] == color[i - 1]) {
            dis2 = i - n;
            c2 = color[i];
            break;
        }
    }
    if(dis1 == INF && dis2 == INF) {
        return color[1];
    }
    if(dis1 < dis2) {
        return c1;
    }
    return c2;
}

int main() {
    cin >> n;
    for (int i = 1; i <= 2 * n - 1; ++i) {
        cin >> a[i];
    }
    int l = 1 , r = 2 * n;
    while(l < r - 1) {
        int m  = (l + r) / 2;
        if(check(m) == 0) {
            r = m;
        }
        else{ 
            l = m;
        }
    }
    cout << l << endl;
}

Measured memory_bytes: 1792
from heapq import heappush, heappop
sx,sy,gx,gy=map(int,input().split())
n=int(input())
g = [[] for i in range(n+2)]
data=[(sx+sy*1j,0)]
for i in range(n):
    a,b,c=map(int,input().split())
    data.append((a+b*1j,c))
data.append((gx+gy*1j,0))

for i in range(n+2):
    for j in range(i+1,n+2):
        tmp=abs(data[i][0]-data[j][0])-data[i][1]-data[j][1]
        g[i].append((tmp,j))
        g[j].append((tmp,i))

dist=[2828427127 for i in range(n+2)]
visited=[False for i in range(n+2)]
dist[0]=0
que=[]
heappush(que,(0,0))

while que:
    c,v=heappop(que)
    if visited[v]:
        continue
    visited[v]=True
    for x in g[v]:
        if visited[x[1]]:
            continue
        tmp=x[0]+c if not x[0]<0 else c
        if tmp<dist[x[1]]:
            dist[x[1]]=tmp
            heappush(que,(tmp,x[1]))
print(dist[n+1])


Measured memory_bytes: 125704
n,m,x=map(int,input().split())
l=[list(map(int, input().split())) for _ in range(n)]

ans=[]
for i in range(2**n):
    t=[0]*m
    cost=0
    for j in range(n):
        if (((i>>j)&1)==1):
            for k in range(m):
                t[k]+=l[j][k+1]
            cost+=l[j][0]
    
    #print('i',i,bin(i),min(t),cost)
    if min(t)>=x:
        ans.append(cost)

if len(ans)==0:
    print(-1)
else:
    print(min(ans))

Measured memory_bytes: 9304
#include<cstdio>
#include<queue>
#include<string.h>
#include<vector>
#include<algorithm>
#include<climits>
using namespace std;

typedef int Weight;
const int INF = 1<<30;

struct Edge {
  int src,dst;
  Weight weight;
  Edge(int src, int dst, Weight weight) :
    src(src), dst(dst), weight(weight) { }
};
bool operator<(const Edge &e, const Edge &f) {
  return e.weight != f.weight ? e.weight > f.weight :
    e.src != f.src ? e.src < f.src : e.dst < f.dst;
}

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;

//dijkstra
//distツづ丑ode sツつゥツづァツづ個催短ツ仰猟猟」ツつェツ禿シツづゥ
void dijkstra(Graph &g, int s, vector<Weight> &dist, vector<int> &prev) {
  int n = g.size();
  dist.assign(n, INF);
  dist[s] = 0;
  prev.assign(n, -1);
  priority_queue<Edge> Q;

  for(Q.push(Edge(-2, s, 0)); !Q.empty(); ) {
    Edge e = Q.top();
    Q.pop();
    if(prev[e.dst] != -1) continue;
    prev[e.dst] = e.src;
    for(Edges::iterator it = g[e.dst].begin(); it != g[e.dst].end(); ++it) {
      if(dist[it->dst] > e.weight + it->weight) {
	dist[it->dst] = e.weight + it->weight;
	Q.push(Edge(it->src, it->dst, e.weight + it->weight));
      }
    }
  }
}

int map[8][8];
int tmap[8][8];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int w,h;

void bfs(int i,int j) {
  queue< pair<int,int> > Q;
  Q.push( pair<int,int>(i,j) );
  while(!Q.empty()) {
    pair<int,int> p = Q.front();
    Q.pop();
    int x = p.first, y = p.second;
    for(int k=0; k<4; ++k) {
      if((x+dx[k] >= 0 && x+dx[k] < h) &&
	 (y+dy[k] >= 0 && y+dy[k] < w)) {
	if((map[x+dx[k]][y+dy[k]] == 1 || map[x+dx[k]][y+dy[k]] > 10
	    || map[x+dx[k]][y+dy[k]] == 3)
	   && tmap[x+dx[k]][y+dy[k]] >= 4000) {
	  tmap[x+dx[k]][y+dy[k]] = tmap[x][y]+1;
	  Q.push( pair<int,int>(x+dx[k], y+dy[k]) );
	}
      }
    }
  }

  return;
}

int main() {
  int count,target;
  while(scanf("%d %d", &w, &h), w|h) {
    memset(map, 0, sizeof(map));
    count=11;
    for(int i=0; i<h; ++i)
      for(int j=0; j<w; ++j) {
	scanf("%d", &map[i][j]);
	if(map[i][j] == 4) {
	  map[i][j] = count;
	  count++;
	}
      }

    Graph g(2+(count-1)-10);
    for(int i=0; i<h; ++i)
      for(int j=0; j<w; ++j) {
	if(map[i][j] == 2 || map[i][j] > 10) {
	  for(int k=0; k<h; ++k)
	    for(int l=0; l<w; ++l)
	      tmap[k][l] = INT_MAX/2;
	  if(map[i][j] == 2) target = 0;
	  else target = map[i][j]-10;
	  tmap[i][j] = 0;
	  bfs(i,j);
	  for(int k=0; k<h; ++k) {
	    for(int l=0; l<w; ++l) {
	      if(k == i && l == j) continue;
	      if(map[k][l] > 10 && tmap[k][l] < 6)
		g[target].push_back(Edge(target,map[k][l]-10,tmap[k][l]));
	      else if(map[k][l] == 3 && tmap[k][l] < 6)
		g[target].push_back(Edge(target,g.size()-1,tmap[k][l]));
	    }
	  }
	}
      }

    vector<Weight> dist(g.size());
    vector<int> prev(g.size());
    dijkstra(g,0,dist,prev);
    printf("%d\n",(dist[g.size()-1] == 1<<30) ? -1 : dist[g.size()-1]);
  }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i <(n); ++i)
#define REP2(i,x,n) for (int i = x; i <(n); ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int,int>;
static const double PI = acos(-1);
static const int INF = 1e9+7;

int query(int i){
    cout << i << endl;
    string s;
    cin >> s;
    if(s == "Male") return 1;
    else if(s == "Female") return 2;
    else exit(0);
}

int main(){
  int n; cin >> n;
  vector<int> s(n);

  int l = 0;
  int r = n-1;

  s[l] = query(l);
  s[r] = query(r);


  while(1){
      int mid = (l + r) / 2;
      s[mid] = query(mid);

      if(s[l] != s[mid] && (mid - l) % 2 == 0) {
          r = mid;
      }
      else if(s[l] == s[mid] && (mid - l) % 2 == 1){
          r = mid;
      }
      else{
          l = mid;
      }
  }
  return 0;
}


Measured memory_bytes: 4000
def stuck(array):
	order=[]
	while array:
		r = len(array)
		w = sum([array[i][1] for i in range(r)])
		mx = 0
		for i in range(r):
			if array[i][2] >= w-array[i][1] and array[i][1] > mx:
				mx = array[i][1]
				id = i
		order.append(array.pop(id)[0])
	return order

def change(a):
	return a[0],int(a[1]),int(a[2])
	
while 1:
	n = input()
	if n == 0:break
	lunch = [change(raw_input().split()) for i in range(n)]
	ans = stuck(lunch)
	for i in range(n):
		print ans[i]

Measured memory_bytes: 4256
s = int(input())
def func(n):
    if n % 2 == 0:
        return n // 2
    else:
        return 3*n + 1
a = [0,s]
for i in range(2,10**6+1):
    a_i = func(a[i-1])
    if a_i in a:
        print(i)
        break
    a.append(a_i)

Measured memory_bytes: 2940
result = list()
while(True):
    score = list(map(int,input().split()))

    if sum(score) == -3:
        break
    if score[0] == -1 or score[1] == -1:
        result.append("F")
    elif score[0]+score[1] >= 80:
        result.append("A")
    elif score[0]+score[1] >= 65:
        result.append("B")
    elif score[0]+score[1] >= 50:
        result.append("C")
    elif score[0]+score[1] >= 30:
        if score[2] >= 50:
            result.append("C")
        else:
            result.append("D")
    else:
        result.append("F")
for i in range(len(result)):
    print(result[i])


Measured memory_bytes: 5596
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;

#define FOR(i,a,b) for(long long int i=(a);i<(b);i++)
#define REP(i,n) for(long long int i=0;i<(n);i++)

#define PI 3.14159265358479

int main(){
	int n;
	vector<double> x, y, z;
	double d1 = 0, d2 = 0, d3 = 0, d = 0;
	cin >> n;
	REP(i, n){
		double dx;
		cin >> dx;
		x.push_back(dx);
	}
	REP(i, n){
		double dy;
		cin >> dy;
		y.push_back(dy);
	}

	REP(i, n){
		z.push_back(x[i] - y[i]);
		if (z[i] < 0)z[i] = -z[i];
		d1 += z[i];
	} 
	z.clear();

	REP(i, n){
		z.push_back(x[i] - y[i]);
		if (z[i] < 0)z[i] = -z[i];
		z[i] = powl(z[i], 2.0);
		d2 += z[i];
	}
	d2 = powl(d2, 0.5);
	z.clear();

	REP(i, n){
		z.push_back(x[i] - y[i]);
		if (z[i] < 0)z[i] = -z[i];
		z[i] = powl(z[i], 3.0);
		d3 += z[i];
	}
	d3 = powl(d3, 0.33333333333333333333333);
	z.clear();

	REP(i, n){
		z.push_back(x[i] - y[i]);
		if (z[i] < 0)z[i] = -z[i];
		if (d < z[i])d = z[i];
	}
	z.clear();

	cout << fixed << d1 << "\n" << d2 << "\n" << d3 << "\n" << d << "\n";
	return 0;
}

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

using namespace std;

int main(void)
{
    int N;
    string s;
    cin >> N;
    set<string> v;

    for(int i = 0; i < N; i++) {
        cin >> s;
        v.insert(s);
    }

    cout << v.size() << endl;
    return 0;

}

Measured memory_bytes: 19128
using System;

namespace ALDS1_5_D_hanten
{
    class Program
    {
        static long count;

        static void Main(string[] args)
        {
            int n = getint();
            var input = getsplit();
            int[] A = Array.ConvertAll(input, int.Parse);
            mergesort(A, 0, n);
            Console.WriteLine(count);
        }
        static void merge(int[] A, int left, int mid, int right)
        {
            int n1 = mid - left;
            int n2 = right - mid;
            var L = new int[n1 + 1];
            var R = new int[n2 + 1];
            int i;
            for (i = 0; i < n1; i++)
            {
                L[i] = A[left + i];
            }
            for (i = 0; i < n2; i++)
            {
                R[i] = A[mid + i];
            }
            L[n1] = int.MaxValue;
            R[n2] = int.MaxValue;
            i = 0;
            int j = 0;
            for (int k = left; k < right; k++)
            {
                if (L[i] <= R[j])
                {
                    A[k] = L[i];
                    i = i + 1;
                }
                else
                {
                    A[k] = R[j];
                    j = j + 1;
                    count += n1 - i;
                }
                
            }
        }
        static void mergesort(int[] A, int left, int right)
        {
            if (left + 1 < right)
            {
                int mid = (left + right) / 2;
                mergesort(A, left, mid);
                mergesort(A, mid, right);
                merge(A, left, mid, right);
            }
        }

        public static string[] getsplit()
        {
            string[] x = Console.ReadLine().Split(' ');
            return x;
        }
        public static int getint()
        {
            int x = int.Parse(Console.ReadLine());
            return x;
        }
    }
}

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

int main() {
  int x, y, z;
  scanf("%d %d %d", &x, &y, &z);
  if (x == y && y == z) {
    printf("1");
  } else if (x == y || y == z || z == x) {
    printf("2");
  } else {
    printf("3");
  }
}


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

namespace AtCoder.Abc
{
    class QuestionD
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            // 整数の入力
            long n = long.Parse(Console.ReadLine());

            // 整数配列の入力
            var inputLongArray = Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();

            long[] count = new long[n +1];
            foreach (var item in inputLongArray)
            {
                count[item]++;
            }

            var c = new long[n + 1];
            for (int i = 0; i < n + 1; i++)
            {
                c[i] = count[i] * (count[i] - 1) / 2;
            }

            // ボールを除かないときの方法の数
            var sum = c.Sum();

            foreach (var a in inputLongArray)
            {
                if (count[a] == 0) continue;
                var newCount = count[a] - 1;
                var ans = sum - c[a] + (newCount * (newCount - 1) / 2);
                Console.WriteLine(ans);
            }
            Console.Out.Flush();
        }
    }
}


Measured memory_bytes: 41024
#include <iostream>
#include <vector>

template <int MOD>
struct ModInt {
    using lint = long long;
    int val;

    // constructor
    ModInt(lint v = 0) : val(v % MOD) {
        if (val < 0) val += MOD;
    };

    // unary operator
    ModInt operator+() const { return ModInt(val); }
    ModInt operator-() const { return ModInt(MOD - val); }
    ModInt inv() const { return this->pow(MOD - 2); }

    // arithmetic
    ModInt operator+(const ModInt& x) const { return ModInt(*this) += x; }
    ModInt operator-(const ModInt& x) const { return ModInt(*this) -= x; }
    ModInt operator*(const ModInt& x) const { return ModInt(*this) *= x; }
    ModInt operator/(const ModInt& x) const { return ModInt(*this) /= x; }
    ModInt pow(lint n) const {
        auto x = ModInt(1);
        auto b = *this;
        while (n > 0) {
            if (n & 1) x *= b;
            n >>= 1;
            b *= b;
        }
        return x;
    }

    // compound assignment
    ModInt& operator+=(const ModInt& x) {
        if ((val += x.val) >= MOD) val -= MOD;
        return *this;
    }
    ModInt& operator-=(const ModInt& x) {
        if ((val -= x.val) < 0) val += MOD;
        return *this;
    }
    ModInt& operator*=(const ModInt& x) {
        val = lint(val) * x.val % MOD;
        return *this;
    }
    ModInt& operator/=(const ModInt& x) { return *this *= x.inv(); }

    // compare
    bool operator==(const ModInt& b) const { return val == b.val; }
    bool operator!=(const ModInt& b) const { return val != b.val; }

    // I/O
    friend std::istream& operator>>(std::istream& is, ModInt& x) noexcept { return is >> x.val; }
    friend std::ostream& operator<<(std::ostream& os, const ModInt& x) noexcept { return os << x.val; }
};

constexpr int MOD = 1e9 + 7;
using mint = ModInt<MOD>;

template <class T>
struct Combination {
    int max_n;
    std::vector<T> f, invf;

    explicit Combination(int n)
        : max_n(n), f(n + 1), invf(n + 1) {
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            f[i] = f[i - 1] * i;
        }

        invf[max_n] = f[max_n].inv();
        for (int i = max_n - 1; i >= 0; --i) {
            invf[i] = invf[i + 1] * (i + 1);
        }
    }

    T fact(int n) const { return f[n]; }
    T invfact(int n) const { return invf[n]; }
    T perm(int a, int b) const {
        return a < b || b < 0 ? T(0) : f[a] * invf[a - b];
    }
    T comb(int a, int b) const {
        return a < b || b < 0 ? T(0) : f[a] * invf[a - b] * invf[b];
    }
};

Combination<mint> C(300000);

void solve() {
    int n, k;
    std::cin >> n >> k;

    mint ans = 0;
    for (int x = 0; x <= k && x < n; ++x) {
        ans += C.comb(n, x) * C.comb(n - 1, n - x - 1);
    }
    std::cout << ans << std::endl;
}

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

    solve();

    return 0;
}


Measured memory_bytes: 2560
N,L =map(int, input().split())
goukei = 0
ans =0
agi_list=[]
for i in range(N):
    agi = L+i
    agi_list.append(agi)
    goukei = agi +goukei
    
if L>0:
    ans = goukei-min(agi_list)
elif L==0:
    ans =goukei
elif (N > abs(L)) :
    ans = goukei
else:
    ans = goukei-(max(agi_list))
print(ans)

Measured memory_bytes: 3064
def main():
    N, W = map(int, input().split())
    VMAX = int(1e5)+1
    dp = [[float("inf")] * (VMAX) for _ in range(2)]
    dp[0][0] = 0
    for i in range(N):
        w, v = map(int, input().split())
        for j in range(VMAX):
            dp[(i+1) % 2][j] = min(dp[i % 2][j], dp[i % 2][max(j-v, 0)]+w)
    left = 0
    right = VMAX
    while left < right:
        center = (left + right) // 2
        if dp[N % 2][center] <= W:
            left = center + 1
        else:
            right = center
    print(left-1)


if __name__ == "__main__":
    main()


Measured memory_bytes: 94524
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static int n = sc.nextInt();
    static int h[] = new int[n];
    static int dp[] = new int[n];

    public static void main(String[] args) {
        //初期化
        for (int i = 0; i < n; i++)
            h[i] = sc.nextInt();
        for (int i = 0; i < n; i++)
            dp[i] = 2147483647;
        dp[0] = 0;
        for (int i = 1; i < n; i++){
            dp[i] = chmin(dp[i], dp[i - 1] + Math.abs(h[i] - h[i - 1]));
            if (i > 1){
                dp[i] = chmin(dp[i], dp[i - 2] + Math.abs(h[i] - h[i - 2]));
            }
        }
        System.out.println(dp[n - 1]);
    }
    public static int chmin(int a, int b){
        if (a > b)
            return b;
        else
            return a;
    }
}


Measured memory_bytes: 51904
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair

using namespace std;

const int INF = 2000000000;
const double pi = 3.1415926;
const int base = 1000000007;

int n, k;
long double ans, p[200000], tek;


int main()
{
    //ifstream cin ("input.txt");
    //ofstream cout ("output.txt");
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.precision(20);
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> p[i];
        p[i] = (p[i] - 1) / 2 + 1;
    }
    //sort(p, p + n);
    for (int i = 0; i < k; i++)
    {
        tek += p[i];
    }
    ans = max(ans, tek);
    for (int i = k; i < n; i++)
    {
        tek += p[i];
        tek -= p[i - k];
        ans = max(ans, tek);
    }
    cout << ans;
    //cout << (long double)1000000000000.8935963;
    //printf("%f", ans);
    return 0;
}

Measured memory_bytes: 3456
#include <stdio.h>
//#include <stdlib.h>
//#include <string.h>
//#include <limits.h>
//#include <math.h>

int main() {
  int n;
  scanf("%d", &n);
  int s = 0, m = n;
  while (m != 0) {
    s += m%10;
    m /= 10;
  }
  if (n%s == 0) printf("Yes\n");
  else printf("No\n");
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll n, a[110000], res;
int main(void){
    // Your code here!
    cin >> n;
    for (ll i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);
    for (ll i = 0; i < n - 1; i++) {
        if (a[i] * 2 < a[i + 1]) {
            res = 0;
        } else {
            res++;
        }
        a[i + 1] += a[i];
    }
    cout << res + 1 << endl;
}


Measured memory_bytes: 1024
// {{{ Boilerplate Code <--------------------------------------------------
// vim:filetype=cpp:foldmethod=marker:foldmarker={{{,}}}

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>

#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define ALL(A)     (A).begin(), (A).end()

using namespace std;

// }}}

int main(){
	int n;
	vector <int> d;

	cin>>n;

	FOR(i,0,n){
		int tmp;
		cin>>tmp;
		d.push_back(tmp);
	}

	vector <int> cands;

	FOR(start,0,n){
		int t=0;
		FOR(i,0,4){
			if(start+i>=n)
				break;

			t=t*10+d[start+i];
			cands.push_back(t);
		}
	}
	sort(ALL(cands));
	
	int prev=-1;

	FOR(i,0,cands.size()){
		if(cands[i]==prev)
			continue;

		if(cands[i]==prev+1){
			prev=cands[i];
			continue;
		}

		cout<<prev+1<<endl;
		return 0;
	}
	cout<<cands[cands.size()-1]+1<<endl;

}

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

class _Class
{
	void _()
	{
		var _ = _Ns();



		var a = "";

		var x = _[2] - _[0];
		var y = _[3] - _[1];

		//
		if (y >= 0)
		{
			for (int i = 0; i < y; i++)
			{
				a+="U";
			}
		}
		else
		{
			for (int i = 0; i < Math.Abs(y); i++)
			{
				a += "D";
			}
		}
		if (x >= 0)
		{
			for (int i = 0; i < x; i++)
			{
				a += "R";
			}
		}
		else
		{
			for (int i = 0; i < Math.Abs(x); i++)
			{
				a += "L";
			}
		}
		//
		if (y >= 0)
		{
			for (int i = 0; i < y; i++)
			{
				a += "D";
			}
		}
		else
		{
			for (int i = 0; i < Math.Abs(y); i++)
			{
				a += "U";
			}
		}
		if (x >= 0)
		{
			for (int i = 0; i < x; i++)
			{
				a += "L";
			}
		}
		else
		{
			for (int i = 0; i < Math.Abs(x); i++)
			{
				a += "R";
			}
		}

		//3
		if (x >= 0)
		{

				a += "L";

		}
		else
		{

				a += "R";

		}

		if (y >= 0)
		{
			for (int i = 0; i < y; i++)
			{
				a += "U";
			}
		}
		else
		{
			for (int i = 0; i < Math.Abs(y); i++)
			{
				a += "D";
			}
		}

		if (y>=0)
		{
				a += "U";
		}
		else
		{

				a += "D";
		}

		if (x >= 0)
		{
			a += "R";
		}
		else
		{
			a += "L";
		}
		if (x >= 0)
		{
			for (int i = 0; i < x; i++)
			{
				a += "R";
			}
		}
		else
		{
			for (int i = 0; i < Math.Abs(x); i++)
			{
				a += "L";
			}
		}
		if (y>=0)
		{
			a += "D";
		}
		else
		{

			a += "U";
		}

		// 4


		if (x >= 0)
		{

			a += "R";

		}
		else
		{

			a += "L";

		}

		if (y >= 0)
		{
			for (int i = 0; i < y; i++)
			{
				a += "D";
			}
		}
		else
		{
			for (int i = 0; i < Math.Abs(y); i++)
			{
				a += "U";
			}
		}

		if (y >= 0)
		{
			a += "D";
		}
		else
		{

			a += "U";
		}
		if (x >= 0)
		{
			a += "L";
		}
		else
		{
			a += "R";
		}
		if (x >= 0)
		{
			for (int i = 0; i < x; i++)
			{
				a += "L";
			}
		}
		else
		{
			for (int i = 0; i < Math.Abs(x); i++)
			{
				a += "R";
			}
		}
		if (y >= 0)
		{
			a += "U";
		}
		else
		{

			a += "D";
		}

		Console.WriteLine(a);
	}

	static void Main(string[] args)
  {
    new _Class()._();
  }

  #region

  string _S()
  {
    return Console.ReadLine();
  }

  string[] _Ss()
  {
    return Console.ReadLine().Split();
  }

  int[] _N(int n)
  {
    var x = new int[n];
    for (var i = 0; i < n; i++)
    {
      x[i] = int.Parse(Console.ReadLine());
    }
    return x;
  }

  int[] _Ns()
  {
    var ss = Console.ReadLine().Split();

    var x = new int[ss.Length];
    for (var i = 0; i < ss.Length; i++)
      x[i] = int.Parse(ss[i]);

    return x;
  }
  #endregion
}


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

#define FOR(i,l,r) for(int i = (int) (l);i < (int) (r);i++)
template<typename T> bool chmax(T& a,const T& b){ return a < b ? (a = b,true) : false; }
template<typename T> bool chmin(T& a,const T& b){ return b < a ? (a = b,true) : false; }
typedef long long ll;

int N,M;
const int MAX_N = 200000;
int b [MAX_N];

int main()
{
	scanf("%d%d",&N,&M);
	FOR(i,0,M){
		int u,v;
		scanf("%d%d",&u,&v);
		u--;
		v--;
		if(u > v) swap(u,v);
		if(u == 0) b [v] |= 1;
		if(v == N - 1) b [u] |= 2;
	}

	bool ans = false;
	FOR(i,0,N){
		ans |= b [i] == 3;
	}
	puts(ans ? "POSSIBLE" : "IMPOSSIBLE");

	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define ff first
#define ss second
#define ll long long
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;

int main() {
#ifndef ONLINE_JUDGE
   freopen("inp.txt", "r", stdin);      freopen("outp.txt", "w", stdout);
#endif
   ios::sync_with_stdio(false);   cin.tie(NULL);   cout.tie(NULL);

   int n;
   cin >> n;
   ll d, x, y, res = 0;
   cin >> d;
   for (int i = 0; i < n; i++) {
      cin >> x >> y;
      if (x * x + y * y <= d * d)
         res++;
   }
   cout << res << '\n';

   return 0;
}

Measured memory_bytes: 3644
n=int(input())
a=[int(input()) for i in range(n)]
a+=[0]

ans=0
for i in range(n):
    pair=a[i]//2
    ans+=pair
    a[i]-=2*pair
    if a[i]>0 and a[i+1]>0:
        ans+=1
        a[i]-=1
        a[i+1]-=1

print(ans)



Measured memory_bytes: 7072
n, p = map(int, input().split())

if n == 1:
    print(p)

else:
    factors = {}
    for i in range(2, int(p**0.5)+1):
        cnt = 0
        while p % i == 0:
            cnt += 1
            factors[i] = cnt
            p //= i

    if factors == {}:
        factors[p] = 1

    ans = 1
    for k, v in factors.items():
        if v >= n:
            ans *= k**(v//n)

    print(ans)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int n,r,l;
int d,t,x;
int tt[1000001]={0},ten[1000001]={0};
typedef pair<int,int> P;
priority_queue<P> qu;
int main(void)
{
	int i,j,flg,max,min,n1,nn,ten1;
	P ppp;
	
	cin>>n>>r>>l;
	
	n1=1;
	ten1=0;
	
	for(i=0;i<r;i++){
		cin>>d>>t>>x;
		
		tt[n1]+=t-ten1;
		ten[d]+=x;
		
		qu.push(P(ten[d],d*-1));
		ten1=t;
		
		while(1){
			ppp=qu.top();
			nn=ppp.second*-1;
			if(ten[nn]==ppp.first){
				n1=nn;
				break;
			}
			qu.pop();
		}	
	}
	
	tt[n1]+=l-ten1;
	max=-1,min=0;
	for(i=1;i<=n;i++){
		if(max<tt[i]){
			max=tt[i];
			min=i;
		}
	}	
	
	cout<<min<<endl;	
}		


Measured memory_bytes: 11700
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC push_options
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#include <xmmintrin.h>
#include <immintrin.h>
using namespace::std;
__attribute__((constructor))void init(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>
// namespace mp = boost::multiprecision;
// typedef mp::number<mp::cpp_dec_float<0>> cdouble;
// typedef mp::cpp_int cint;
template<typename T>using pbds=__gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
template<typename T>using pbds_map=__gnu_pbds::tree<T,T,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
template<typename T,typename E>using hash_map=__gnu_pbds::gp_hash_table<T,E>;
template<typename T>using pqueue =__gnu_pbds::priority_queue<T, greater<T>,__gnu_pbds::rc_binomial_heap_tag>;
typedef long long lint;
#define INF (1LL<<60)
#define IINF (1<<30)
#define EPS (1e-10)
#define endl ('\n')
//#define MOD 1000000007LL
#define MOD 998244353LL
typedef vector<lint> vec;
typedef vector<vector<lint>> mat;
typedef vector<vector<vector<lint>>> mat3;
typedef vector<string> svec;
typedef vector<vector<string>> smat;
template<typename T>inline void numout(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<<i<INF/2?i:"INF";f=1;}cout<<endl;}
template<typename T>inline void numout2(T t){for(auto i:t)numout(i);}
template<typename T>inline void output(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<<i;f=1;}cout<<endl;}
template<typename T>inline void output2(T t){for(auto i:t)output(i);}
template<typename T>inline void _output(T t){bool f=0;for(lint i=0;i<t.size();i++){cout<<f?"":" "<<t[i];f=1;}cout<<endl;}
template<typename T>inline void _output2(T t){for(lint i=0;i<t.size();i++)output(t[i]);}
#define rep(i,n) for(lint i=0;i<lint(n);++i)
#define repi(i,a,b) for(lint i=lint(a);i<(lint)(b);++i)
#define rrep(i,n) for(lint i=lint(n)-1;i>=0;--i)
#define rrepi(i,a,b) for(lint i=lint(b)-1;i>=lint(a);--i)
#define irep(i) for(lint i=0;;++i)
#define all(n) begin(n),end(n)
#define dist(a,b,c,d) sqrt(pow(a-c,2)+pow(b-d,2))
inline lint gcd(lint A,lint B){return B?gcd(B,A%B):A;}
inline lint lcm(lint A,lint B){return A/gcd(A,B)*B;}
// inline cint cgcd(cint A,cint B){return B?cgcd(B,A%B):A;}
// inline cint clcm(cint A,cint B){return A/cgcd(A,B)*B;}
inline bool chmin(auto& s,const auto& t){bool res=s>t;s=min(s,t);return res;}
inline bool chmax(auto& s,const auto& t){bool res=s<t;s=max(s,t);return res;}
const vector<lint> dx={1,0,-1,0,1,1,-1,-1};
const vector<lint> dy={0,1,0,-1,1,-1,1,-1};
#define SUM(v) accumulate(all(v),0LL)
auto call=[](auto f,auto... args){return f(f,args...);};

int main(){
    lint x,y,z;
    cin>>x>>y>>z;
    cout<<z<<" "<<x<<" "<<y<<endl;
}

Measured memory_bytes: 256
using System;
using System.Text;

class Program
{
    static void Main()
    {
        var s = Console.ReadLine();
        var s2 = new StringBuilder();
        for (int i=0; i<s.Length; i+=2)
        {
            s2.Append(s[i]);
        }
        Console.WriteLine(s2);
    }
}

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

int main() {

  int K;
  string S;
  cin >> K >> S;
  if(S.size() <= K){
    cout << S << endl;
  }else{
    for(int i = 0; i < K; i++){
    cout << S.at(i);
    }
    cout << "..." << endl;
  }
  
}


Measured memory_bytes: 3628