akhauriyash/Code-Regression huggingface dataset:
S = input()
K = int(input())
key = 0
i = 0
while True:
    if i >= K:
        break
    if i >= len(S):
        break
    if int(S[i]) != 1:
        print(S[i])
        key = 1
        break
    i += 1

if key == 0:
    print(S[0])


Measured memory_bytes: 2940
#include<iostream>
#include<cmath>
#include<algorithm>

using namespace std;

int main(){
	long long a,g,t;
  	cin>>a;
  	cin>>t;
  	for(int i=0;i<a-1;i++) {
      cin>>g;t=__gcd(t,g);
    }
  	cout<<t;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <sstream>
#include <cmath>
#include <math.h>
#include <string>
using namespace std;
typedef long long ll;
#define rep(n) for( int i = 0 ; i < n ; i++ )
#define REP(n) for( int i = 1 ; i <= n ; i++ )
#define repll(n) for( ll i = 0 ; i < n ; i++ )
#define REPll(n) for( ll i = 1 ; i <= n ; i++ )

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n , k;
  	cin >> n >> k;
  	ll ans = ( n / k ) * ( n / k ) * ( n / k );
	if ( k % 2 == 1 ) cout << ans;
	else {
		ll c = ( n + ( k / 2 ) ) / k;
		cout << ans + c * c * c;
	}
}


Measured memory_bytes: 3640
#define D(x) cout << #x " = " << x << endl
#define DD(x, y) cout << "(" #x ", " #y ") = (" << x << ", " << y << ")" << endl
#define DDD(x, y, z) cout << "(" #x ", " #y ", " #z ") = (" << x << ", " << y << ", " << z << ")" << endl
#define DV(v) for (auto __macro_vi : v){ cout << __macro_vi << " ";} cout << endl;
#define DA(a, n) for (int __macro_i = 0; __macro_i < n; ++__macro_i) { cout << a[__macro_i] << " "; } cout << endl;
#define REP(i, n) for (int i = 0; i < n; ++i)
#define ALL(v) (v).begin(), (v).end()
#include<iostream>
#include<vector>
#include<cassert>
#include<cmath>

using namespace std;
using ll = long long;
const ll mx = 1000000000;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll s;
    cin >> s;
    ll w = (int)(ceil(sqrt(s)));
    if (w > mx) w = mx;
    ll left = w * w - s;
    if (w * w < s) w++;
    if ((w - 1) * (w - 1) >= s) w--;
    ll y1 = left != 0 ? 1 : 0;
    ll x2 = left != 0 ? left : 0;
    ll ans[] = {0, 0, w, y1, x2, w};
    assert(abs(w * w - y1 * x2) == s);
    assert(w <= mx && y1 <= mx && x2 <= mx);
    cout << ans[0];
    for (int i = 1; i < 6; ++i) {
        cout << " " << ans[i];
    }
    cout << endl;
}


Measured memory_bytes: 888
/* Search II */
#include<stdio.h>
int main(){
  int n,q; /* n: S, q: T */
  int S[100001],T[50001]; /* n<=100000, q<=50000 */
  int i,j,counter=0;
  int left, mid, right;

  scanf("%d", &n);
  for(i=0;i<n;i++){
    scanf("%d", &S[i]);
  }
  scanf("%d", &q);
  for(i=0;i<q;i++){
    scanf("%d", &T[i]);
  }

  /* Binary Search */
  /* S:A, T:key */
  for(i=0;i<q;i++){
    left=0;
    right=n;
    while(left<right){
      mid=(left+right)/2;
      if(S[mid]==T[i]){
        counter++;
        break;
      }else if(S[mid]<T[i]){
        left=mid+1;
      }else{
        right=mid;
      }
    }
  }
  printf("%d\n",counter);
  return 0;
}

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

int main()
{
	int n;
	cin >> n;
	long long int x, y;
	x = y = 1;
	for(auto i = 0; i < n; ++i){
		long long int s, t, ax, ay, bx, by;
		cin >> s >> t;
		ax = (x + s - 1) / s * s;
		ay = (x + s - 1) / s * t;
		bx = (y + t - 1) / t * s;
		by = (y + t - 1) / t * t;
		if(ay >= y){
			x = ax;
			y = ay;
		}else{
			x = bx;
			y = by;
		}
	}
	cout << x + y << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define FOR(i, x, y) for(int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, k;
    cin >> n >> k;
    ll rem = n / k;
    ll ans = rem * rem * rem;
    if (k & 1) cout << ans << '\n';
    else {
        ll rem = (n + k / 2) / k;
        ans += rem * rem * rem;
        cout << ans << '\n';
    }
    return 0;
}

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

int main() {
  int n;
  cin >> n;
  vector<pair<string, pair<int, int>>> a(n);
  for(int i=0; i<n; i++) {
    cin >> a.at(i).first >> a.at(i).second.first;
    a.at(i).second.first *= -1;
    a.at(i).second.second = i + 1;
  }
  
  sort(a.begin(), a.end());
  
  for(int i=0; i<n; i++) {
    cout << a.at(i).second.second << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    int n,i,a[1000];
    cin>>n;
    for(i=0;i<n;i++)
        cin>>a[i];
    for(i=0;i<n;i++)
    {
        if(a[i]%2==0)
        {
            if(a[i]%3==0 || a[i]%5==0)
                continue;
            else
                break;
        }
    }
    if(i<n)
        cout<<"DENIED";
    else
        cout<<"APPROVED";
}


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

int main(){
  string s;
  cin >> s;
  vector<string> a = {"AKIHABARA", "AKIHABAR", "AKIHABRA", "AKIHBARA", "KIHABARA",
                      "AKIHABR", "AKIHBAR", "AKIHBRA", "KIHABAR", "KIHBAR", "KIHABRA",
                      "AKIHBR", "KIHABR", "KIHBAR", "KIHBRA", "KIHBR"};
  for(int i = 0; i < 16; i++){
    if(s == a[i]) {cout << "YES" << endl; return 0;}
  }
  cout << "NO" << endl;
  return 0;
}

Measured memory_bytes: 3620
#include<stdio.h>


int main()
{
	long n,k,x,y,z,m;
	long i, j;
	scanf("%ld %ld", &n,&k);
	for (i = 0; i < n; i++) {
		if (i == 0) {
			scanf("%ld", &y);
			m = y;
			continue;
		}
		scanf("%ld",&x);
		if (x>m) {
			m = x;
		}
		if (x < y) {
			z = y;
			y = x;
			x = z;
		}
		while (x%y != 0) {
			z = y;
			y = x%y;
			x = z;
		}
	}
	if (k%y == 0&&k<=m) {
		printf("POSSIBLE");
		}else{
		printf("IMPOSSIBLE");
	}
    return 0;
}

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

#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < n; i++)
typedef long long ll;

int main() {
    string a, b; cin >> a >> b;
    if(b.size() < a.size()){
        cout << "GREATER" << endl;
    }else if(a.size() < b.size()){
        cout << "LESS" << endl;
    }else{
        if(b < a) cout << "GREATER" << endl;
        else if(a < b) cout << "LESS" << endl;
        else cout << "EQUAL" << endl;
    }
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <bitset>
#include <complex>
#include <unistd.h>
#include <cassert>
#include <cctype>
#include <random>
#include <time.h>
#define _USE_MATH_DEFINES
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef pair<double, ll> pdlg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef tuple<double, double, double> tddd;
typedef complex<double> xy_t;
typedef vector<ll> vll;
typedef vector< vector<ll> > matrix;
#define REP(i, x, y) for(ll i = (ll)x; i < (ll)y; i++)
#define DREP(i, x, y, d) for(ll i = (ll)x; i < (ll)y; i += (ll)d)
#define PER(i, x, y) for(ll i = (ll)x; i > (ll)y; i--)
#define DPER(i, x, y, d) for(ll i = (ll)x; i > (ll)y; i -= (ll)d)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
double pi = 3.141592653589793;
ll mod = 1000000007;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;
int iinf = intmax / 8;
ll inf = llmax / 8;
double eps = 1e-12;

ll dp[200010][4];

int main() {
    ll L;
    cin >> L;
    ll A[L];
    ll sum = 0;
    REP(i, 0, L) {
        cin >> A[i];
        sum += A[i];
    }
    REP(i, 0, 200010) {
        fill(dp[i], dp[i] + 4, inf);
    }
    dp[0][0] = sum;
    REP(i, 0, L) {
        dp[i + 1][3] = min(min(dp[i][0], dp[i][1]), min(dp[i][2], dp[i][3]));
        ll min2 = min(min(dp[i][0], dp[i][1]), dp[i][2]);
        if (A[i] >= 2) {
            dp[i + 1][2] = min2 - (A[i] - A[i] % 2);
        } else if (A[i] == 1) {
            dp[i + 1][2] = min2;
        } else {
            dp[i + 1][2] = min2 + 2;
        }
        ll min1 = min(dp[i][0], dp[i][1]);
        if (A[i] >= 1) {
            dp[i + 1][1] = min1 - (A[i] - (A[i] + 1) % 2);
        } else {
            dp[i + 1][1] = min1 + 1;
        }
        ll min0 = dp[i][0];
        if (A[i] >= 2) {
            dp[i + 1][0] = min(min0 - (A[i] - A[i] % 2), sum);
        } else if (A[i] == 1) {
            dp[i + 1][0] = min(min0, sum);
        } else {
            dp[i + 1][0] = min(min0 + 2, sum);
        }
    }
    ll ans = inf;
    REP(i, 0, 4) {
        ans = min(ans, dp[L][i]);
    }
    // REP(i, 0, 3) {
    //     REP(j, 0, L + 1) {
    //         cout << dp[j][i] << " ";
    //     }
    //     cout << endl;
    // }
    cout << ans << endl;
}


Measured memory_bytes: 8064
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<deque>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;

int main()
{
	int N;
	string S[10010];
	cin >> N;
	for (int i = 0; i < N; i++) cin >> S[i];
	int ans = 0;
	int A = 0, B = 0, same = 0;
	for (int i = 0; i < N; i++) {
		if (S[i][0] == 'B') B++;
		if (S[i][S[i].size() - 1] == 'A') A++;
		if (S[i][0] == 'B' && S[i][S[i].size() - 1] == 'A') {
			same++;
			A--; B--;
		}
		for (int j = 0; j < S[i].size(); j++) {
			if (S[i][j] == 'A' && S[i][j + 1] == 'B') ans++;
		}
	}
	if (same == 0) ans += min(A, B);
	else {
		if (A + B > 0) ans += same + min(A, B);
		else ans += same - 1;
	}
	cout << ans << endl;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef vector<vector<int>> Matrix;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
static const int INF = 2000000000;

const int mod = 1000000007;

int main(){
  int k, a, b;
  cin >> k >> a >> b;
  bool ok = false;
  for (int i = a; i <= b; i++){
    if (i % k == 0) ok = true; 
  }
  if (ok) cout << "OK\n";
  else cout << "NG\n";
}

Measured memory_bytes: 3636
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void scan(T...)(ref T a) {
    string[] ss = readln.split;
    foreach (i, t; T) a[i] = ss[i].to!t;
}
T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

void main() {
    readint;
    auto a = readints;

    int m = cast(int)(a.length - 1) / 2; // 中央値の位置
    int left = m; // 中央値の左側の要素数
    auto b = a.dup.sort();

    auto median = b[m];
    auto median1 = b[m + 1];
    foreach (x; a) {
        if (x <= median) writeln(median1);
        else writeln(median);
    }
}


Measured memory_bytes: 12644
#include <assert.h>
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
 
using ll = long long;
using P = std::pair<ll, ll>;
 
#define rep(i, a, b) for (ll(i) = (a); i < (b); i++)
#define all(i) i.begin(), i.end()
#define debug(i) std::cerr << "debug " << #i <<" "<<i<<std::endl;
 
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) {
  return os << pa.first << " " << pa.second;
}
 
template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (int i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}
 
template<typename T1,typename T2>
inline bool chmax(T1& a,T2 b){return a<b && (a=b,true);}
 
template<typename T1,typename T2>
inline bool chmin(T1& a,T2 b){return a>b && (a=b,true);}
 
// const ll MOD = 998244353;
const ll MOD = 1e9 + 7;

ll dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
 
int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  ll n;
  std::cin>>n;

  std::string s;
  std::cin>>s;

  ll q;
  std::cin>>q;

  rep(_,0,q){
    ll k;
    std::cin>>k;

    ll ans=0;

    ll m_cnt=0,c_cnt=0,mnum=0;

    for(ll i=n-1;i>=0;i--){
      if(i<=n-1-k){
        if(s[i+k]=='C'){
          mnum-=m_cnt;
          c_cnt--;
        }else if(s[i+k]=='M'){
          m_cnt--;
        }
      }

      if(s[i]=='D'){
        ans+=mnum;
      }
      if(s[i]=='M'){
        m_cnt++;
        mnum+=c_cnt;
      }
      if(s[i]=='C'){
        c_cnt++;
      }
    }

    std::cout<<ans<<"\n";
  }

  return 0;
}





Measured memory_bytes: 1948
import java.util.*;
public class Main {

	public void doIt(){
		Scanner sc = new Scanner(System.in);
		int [][] data = new int[100][50];
		int k = 0;
		int w = 0;
		while(sc.hasNext()){
			String [] str = sc.next().split(",");
			int len = str.length;
			w = Math.max(w, len);
			for(int i=0; i < len; i++){
				data[k][i] = Integer.parseInt(str[i]);
			}
			k++;
		}
		int h = w * 2 - 1;
		int [][] dp = new int[h][w];
		dp[0][0] = data[0][0];
		for(int i=0; i < w - 1; i++){
			for(int j=0; j <= i; j++){
				int result = dp[i][j] + data[i+1][j];
				dp[i+1][j] = Math.max(result, dp[i+1][j]);

				result = dp[i][j] + data[i+1][j+1];
				dp[i+1][j+1] = Math.max(result, dp[i+1][j+1]);
			}
		}

		for(int i=w; i < h; i++){
			for(int j=0; j < h - i; j++){
				dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j+1]) + data[i][j];

			}
		}
		System.out.println(dp[h-1][0]);
	}
	public static void main(String[] args) {
		Main obj = new Main();
		obj.doIt();
	}
}

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

int main(){
	int N;
	cin >> N;
	int ans=0;
	for(int i=1;i<=N;i++){
		if(0<i && i<10)ans++;
		else if(99<i && i<1000)ans++;
		else if(9999<i && i<100000)ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))

f = {}
right = 0
accum = A[0]
for left in range(N):
    if right < left:
        right = left
        accum = A[left]

    while(right < N-1):
        if accum & A[right+1] == 0:
            accum += A[right+1]
            right += 1
        else:
            break

    f[left] = right
    accum -= A[left]

answer = 0
for i in range(N):
    answer += f[i] - i + 1

print(answer)

Measured memory_bytes: 37372
N=gets.to_i
a=gets.split.map &:to_i
h={}
a.each do |i|
  h[i].nil? ? h[i]=1 : h[i]+=1 
end
[*1..N].each do |i|
  if h[i].nil?
    puts 0
  else
    puts h[i]
  end
end


Measured memory_bytes: 42824
import decimal,math
from collections import Counter,defaultdict
from fractions import gcd
from bisect import bisect_right,bisect_left
decimal.getcontext().prec = 10
n,k=map(int,raw_input().split())
arr=map(int,raw_input().split())
arr = [0]+arr
mod=10**9+7
dp = [] #(n+1)*(k+1) dp
for i in range(n+1):
	ok=[]
	for j in range(k+1):
		ok.append(0)
	dp.append(ok)	
dp[0][0]=1	
for i in range(1,n+1):
	xx=0
	for j in range(k+1):
		if(j-arr[i]-1>=0):
			xx = (xx+dp[i-1][j] - dp[i-1][j-arr[i]-1])%mod
		else:
			xx=(xx+dp[i-1][j])%mod
		dp[i][j] = (xx)%mod	
	# print i,			
print (dp[n][k])%mod

Measured memory_bytes: 140916
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define priq priority_queue<int>
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(int)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(int)(key)))
#define tii tuple<int,int,int>
#define Priq priority_queue<int,vi,greater<int>>
#define pb push_back
#define mp make_pair
#define INF (1ll<<60)
signed main(){
  int N; cin>>N;
  vector<pii> A(N);
  rep(i,0,N){
    cin>>A[i].first;
    A[i].second=i+1;
  }
  sort(ALL(A));
  rep(i,0,N) cout<<A[i].second<<" ";
  cout<<endl;
  }


Measured memory_bytes: 2432
#include <functional>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;
const ll MOD = 1000000007LL;

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

    int x;
    cin >> x;

    vector <bool> dp(200000);
    dp[0] = true;

    for (int i = 0; i < x; i++) {
        if (dp[i]) {
            for (int j = 100; j < 106; j++) {
                dp[i + j] = true;
            }
        }
    }

    cout << (dp[x] ? 1 : 0) << "\n";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define endl '\n'
#define debug(X) cout << #X << " = " << X << endl

using namespace std;

const int MN = 100010;

int par[MN], sz[MN];

int findSet(int i) { return i == par[i] ? i : par[i] = findSet(par[i]); }
void unionSet(int i, int j) { par[findSet(i)] = findSet(j); }

long long f(long long n) { return (n * (n - 1)) / 2; }

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	#ifdef UTP
	freopen("input.txt", "r", stdin);
	#endif
	int n, m; cin >> n >> m;
	vector<int> a(m), b(m);
	for (int i = 0; i < m; i++) {
		cin >> a[i] >> b[i];
		a[i]--; b[i]--;
	}
	for (int i = 0; i < n; i++)
		par[i] = i, sz[i] = 1;
	vector<long long> ans(m);
	long long total = f(n);
	for (int i = m - 1; i >= 0; i--) {
		ans[i] = total;
		if (findSet(a[i]) != findSet(b[i])) {
			total += f(sz[findSet(b[i])]);
			total += f(sz[findSet(a[i])]);
			sz[findSet(b[i])] += sz[findSet(a[i])];
			unionSet(a[i], b[i]);
			total -= f(sz[findSet(b[i])]);
		}
	}
	for (int i = 0; i < m; i++)
		cout << ans[i] << endl;
	return 0;
}


Measured memory_bytes: 3712
#include <iostream>

using namespace std;

int partition(int a[],int b[],int l,int r);
int quicksort(int a[],int b[],int l,int r);

int main(){
  
  int N,a[100005],stu[100005];
  
  cin>>N;
  
  for(int i=0;i<N;i++){
    cin>>a[i];
    stu[i]=i+1;
  }
  
  quicksort(a,stu,0,N-1);
  
  
  for(int i=0;i<N;i++){
    cout<<stu[i]<<" ";
  }
  
 return 0; 
}

int partition(int a[],int b[],int l,int r){
    int i,j,bbuff;
    int abuff,pivot;
    
    i=l-1,j=r;
    pivot=a[r];
    for(;;){
        while(a[++i]<pivot);
        
        while(i<=--j && a[j]>=pivot);
        
        if(i>=j){
            abuff=a[r],a[r]=a[i],a[i]=abuff;
            bbuff=b[r],b[r]=b[i],b[i]=bbuff;
            break;
        }
        
        abuff=a[i],a[i]=a[j],a[j]=abuff;
        bbuff=b[i],b[i]=b[j],b[j]=bbuff;
        
    }
    
    return i;
}

int quicksort(int a[],int b[],int l,int r){
    int v;
    
    if(l>=r){
        return 0;
    }
    
    v=partition(a,b,l,r);
    
    quicksort(a,b,l,v-1);
    quicksort(a,b,v+1,r);
    
    return 0;
    
}


Measured memory_bytes: 1664
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;


int main()
{
	int n;
	int x[100];
	double d1 = 0, d2 = 0, d3 = 0, dinf = -1;
	cin >> n;

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

	for (int i = 0;i < n;i++) {
		int yi;
		cin >> yi;
		yi = abs(x[i] - yi);
		d1 += yi;
		d2 += yi * yi;
		d3 += yi * yi * yi;

		if (yi > dinf) {
			dinf = yi;
		}
	}

	d2 = sqrt(d2);
	d3 = pow(d3, 0.333333333333);

	printf("%lf\n%lf\n%lf\n%f\n", d1, d2, d3, dinf);

    return 0;
}



Measured memory_bytes: 3316
import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))

    ans = [0] * N
    for i, a in enumerate(A):
        ans[0] += (-1)**i * a

    for i in range(1, N):
        ans[i] = A[i-1] * 2 - ans[i-1]

    for a in ans:
        print(a, end=' ')
    print('')


if __name__ == '__main__':
    main()


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


int main(){
  int h,w,a,b;
  cin >> h >> w >> a >> b;
  vector<vector<int>> ans(h,vector<int>(w,0));
  for(int i=0;i<h;++i){
    for(int j=0;j<w;++j){
      if((i<b && j<a) || (i>=b && j>=a)){
        ans[i][j]=1;
      }
    }
  }
  for(int i=0;i<h;++i){
    for(int j=0;j<w;++j){
      cout << ans[i][j];
    }
    cout << endl;
  }
  return 0;
}


Measured memory_bytes: 5120
open System.IO
open System

let [| h; w; a; b; |] = stdin.ReadLine().Split() |> Array.map int

//出力
let sw = new StreamWriter(Console.OpenStandardOutput())
sw.AutoFlush <- false
Console.SetOut(sw)

seq{
    for i in 1..b do
        yield new string ([|
            for i in 1..a -> '0'
            for i in 1..w-a -> '1'|]) 
    for i in 1..h-b do
        yield new string ([|
            for i in 1..a -> '1'
            for i in 1..w-a -> '0' |])
} |> Seq.iter (fun x  -> stdout.WriteLine x)

stdout.Flush()

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

int main(){
  int n;cin>>n;
  string s;cin>>s;
  int j=0;
  if(s.size()%2==1){
    cout<<"No"<<endl;
    return 0;
  }
  for(int i=0;i<s.size()/2;i++){
    if(s.at(i)==s.at(s.size()/2+i))
      j++;
    else
      j--;
  }
  if(j==s.size()/2)
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
  /*string t;
  for(int i=0;i<s.size();i++){
    t.at(i)=s.at(s.size()/2)
    
  }*/
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long int
int32_t main(){
	int ar[3];
	cin>>ar[0]>>ar[1]>>ar[2];sort(ar,ar+3);
	int ans=0;
	if(!((ar[2]-ar[1])&1)){
		ans += (ar[2]-ar[1])/2;
		ar[1]=ar[2];
	}
	else {
		ans++;
		ar[0]++;ar[1]++;
		ans+=(ar[2]-ar[1])/2;
		ar[1]=ar[2];
	}
	if(!((ar[1]-ar[0])&1)){
		ans += (ar[1]-ar[0])/2;
		ar[0]=ar[1];
	}
	else {
		ans++;
		ar[2]++;ar[1]++;
		ans+=(ar[1]-ar[0])/2;
		ar[0]=ar[1];
	}
	cout<<ans;
}


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

// template {{{  0 
// using {{{ 1
using ll = long long int;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
// }}} 1
// definition {{{ 1
// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define Scll(x) scanf("%lld", &x)
#define Scll2(x,y) scanf("%lld%lld", &x, &y)
#define Scll3(x,y,z) scanf("%lld%lld%lld", &x, &y, &z)
#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2
// constants {{{ 2
#define EPS (1e-7)
#define INF (2e9)
#define PI (acos(-1))
// }}} 2
// systems {{{ 2
#define Repe(x,y,z) for(ll x = z; x < y; x++)
#define Rep(x,y) Repe(x,y,0)
#define RRepe(x,y,z) for(ll x = y-z-1; x >= 0; x--)
#define RRep(x,y) RRepe(x,y,0)
// }}} 2
// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n")
#define YESNO(a) (a)?printf("YES\n"):printf("NO\n")
// }}} 2
// }}} 1
// input {{{ 1
// }}} 1
// }}} 0

int main() {

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

    vector<int> p(M);
    vector<string> s(M);
    Rep(i,M) cin >> p[i] >> s[i];

    vector<int> pena(N);
    vector<bool> Ac(N,false);
    Rep(i,M){
        p[i]--;
        if( s[i] == "AC" ) Ac[p[i]] = true;
        if( !Ac[p[i]] && s[i] == "WA" ) pena[p[i]] += 1;
    }

    int pen = 0;
    int ac = 0;
    Rep(i,N){
        if( Ac[i] ) ac++, pen += pena[i];
    }

    printf ("%d %d\n", ac, pen );

    return 0;
}



Measured memory_bytes: 6528
#![allow(unused_parens)]
#![allow(unused_imports)]
#![allow(non_upper_case_globals)]
#![allow(non_snake_case)]
#![allow(unused_mut)]
#![allow(unused_variables)]
#![allow(dead_code)]

use itertools::Itertools;
use proconio::input;
use proconio::marker::{Chars, Usize1};

#[allow(unused_macros)]
#[cfg(debug_assertions)]
macro_rules! mydbg {
    //($arg:expr) => (dbg!($arg))
    //($arg:expr) => (println!("{:?}",$arg));
      ($($a:expr),*) => {
          eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
      }
}
#[cfg(not(debug_assertions))]
macro_rules! mydbg {
    ($($arg:expr),*) => {};
}

macro_rules! echo {
    ($($a:expr),*) => {
          $(println!("{}",$a))*
      }
}

use std::cmp::*;
use std::collections::*;
use std::ops::{Add, Div, Mul, Sub};

#[allow(dead_code)]
static INF_I64: i64 = 92233720368547758;
#[allow(dead_code)]
static INF_I32: i32 = 21474836;
#[allow(dead_code)]
static INF_USIZE: usize = 18446744073709551;
#[allow(dead_code)]
static M_O_D: usize = 1000000007;
#[allow(dead_code)]
static PAI: f64 = 3.1415926535897932;

trait IteratorExt: Iterator {
    fn toVec(self) -> Vec<Self::Item>;
}

impl<T: Iterator> IteratorExt for T {
    fn toVec(self) -> Vec<Self::Item> {
        self.collect()
    }
}

trait CharExt {
    fn toNum(&self) -> usize;
    fn toAlphabetIndex(&self) -> usize;
    fn toNumIndex(&self) -> usize;
}
impl CharExt for char {
    fn toNum(&self) -> usize {
        return *self as usize;
    }
    fn toAlphabetIndex(&self) -> usize {
        return self.toNum() - 'a' as usize;
    }
    fn toNumIndex(&self) -> usize {
        return self.toNum() - '0' as usize;
    }
}

trait VectorExt {
    fn joinToString(&self, s: &str) -> String;
}
impl<T: ToString> VectorExt for Vec<T> {
    fn joinToString(&self, s: &str) -> String {
        return self
            .iter()
            .map(|x| x.to_string())
            .collect::<Vec<_>>()
            .join(s);
    }
}

trait StringExt {
    fn get_reverse(&self) -> String;
}
impl StringExt for String {
    fn get_reverse(&self) -> String {
        self.chars().rev().collect::<String>()
    }
}

trait UsizeExt {
    fn pow(&self, n: usize) -> usize;
}
impl UsizeExt for usize {
    fn pow(&self, n: usize) -> usize {
        return ((*self as u64).pow(n as u32)) as usize;
    }
}

fn f(a: usize, b: usize, x: usize) -> usize {
    (a * x) / b - (a * (x / b))
}

fn main() {
    input! {
       a: usize,
       b:usize,
       n:usize,
    }

    let mut ans: usize = 0;
    ans = max(ans, f(a, b, 1));
    ans = max(ans, f(a, b, n));
    let mut x = 0;
    for i in 1.. {
        x += b * i - 1;
        mydbg!(x);
        if x > n {
            break;
        }
        ans = max(ans, f(a, b, x));
    }

    echo!(ans);
}


Measured memory_bytes: 2064
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PI 3.141592653589793
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n, k) for (int i = (n); i >= (k); i--);
#define all(x) (x).begin(), (x).end()
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<class T>vector<T> make_vector(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto make_vector(size_t a, Ts... ts){return vector<decltype(make_vector<T>(ts...))>(a, make_vector<T>(ts...));}
const int inf = 2e18;
const int mod = 1e9 + 7;

signed main() {
    int N, M;
    cin >> N >> M;
    vector<pair<int, int>> key;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        int s = 0;
        for (int j = 0; j < b; j++) {
            int c;
            cin >> c;
            --c;
            s |= (1LL<<c);
        }
        key.emplace_back(s, a);
    }
    vector<int> dp(1LL<<N, inf);
    dp[0] = 0;
    for (int s = 0; s < (1LL<<N); s++) {
        for (int i = 0; i < M; i++) {
            int t = s | key[i].first; // transition
            dp[t] = min(dp[t], dp[s] + key[i].second);
        }
    }
    int ans = dp.back();
    if (ans == inf) cout << -1 << endl;
    else cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define V vector<long long>
#define VV vector<vector<long long>>
#define VVV vector<vector<vector<long long>>>
#define rep(i,n) for(ll (i)=0;(i)<(n);++(i))
using namespace std;

template<typename T>
struct segment_tree{
    function<T(T,T)> f = [](T a, T b){return min(a,b);};
    T inf=INT_MAX;
    vector<T> value;
    int N;
    segment_tree(int n){
        N=1;
        while(N<n)N*=2;
        value.assign(2*N-1,inf);
    }
    segment_tree(int n, function<T(T,T)> func, T t1){
        N=1;
        while(N<n)N*=2;
        value.assign(2*N-1,t1);
        f=func;
        inf=t1;
    }
    void update(int i,T x){
        i+=N-1;
        value[i]=x;
        while(i>0){
            i=(i-1)/2;
            value[i]=f(value[i*2+1],value[i*2+2]);
        }
    }
    T query(T a,T b){
        return query(a,b,0,0,N);
    }
    T query(T a,T b, int k, int l, int r){
        if(r<=a || b<=l)return inf;
        if(a<=l && r<=b){
            return value[k];
        }else{
            ll c1=query(a,b,2*k+1,l,(l+r)/2);
            ll c2=query(a,b,2*k+2,(l+r)/2,r);
            return f(c1,c2);
        }
    }
    void print(){
        for(int i=0;i<ceil(log2(N))+1;i++){
            for(int j=0;j<(1<<i);j++){
                cout<<value[j+(1<<i)-1]<<((j==(1<<i)-1)?:',');
            }
            cout<<endl;
        }
    }
};

int main() {
    int n,q;
    cin>>n>>q;
    segment_tree<ll> st(n);
    rep(i,q){
        ll c,x,y;
        cin>>c>>x>>y;
        if(c==0){
            st.update(x, y);
        }else{
            cout<<st.query(x,y+1)<<endl;
        }
    }
}



Measured memory_bytes: 4880
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define PI acos(-1)
#define vi vector<int>
#define pi pair<int, int>
#define pl pair<ll, ll>
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
const int MOD = 1e9+ 7;
const int INF = numeric_limits<int>::max() - (int)1e8;
const ll INFLL = numeric_limits<ll>::max() - (ll)1e17;

template<typename M>
class SegmentTree {
private:
    vector<M> data;
    const function<M(M, M)> merge;
    const M identity_element;
    size_t base_data_size;

    void data_size_calc_and_init(size_t N) {
        base_data_size = 1;
        while (base_data_size < N) base_data_size <<= 1;
        data = vector<M>(2 * base_data_size, identity_element);
    }

    void build() {
        for (size_t index = base_data_size - 1; index > 0; index--) {
            data[index] = merge(data[2 * index], data[2 * index + 1]);
        }
    }

public:
    explicit SegmentTree(size_t N, const function<M(M, M)> merge, const M identity_element) : merge(merge), identity_element(identity_element) {
        data_size_calc_and_init(N);
    }

    explicit SegmentTree(const vector<M> &init_data, const function<M(M, M)> merge, const M identity_element) : merge(merge), identity_element(identity_element) {
        data_size_calc_and_init(init_data.size());
        for (size_t index = 0; index < init_data.size(); index++) {
            data[base_data_size + index] = init_data[index];
        }
        build();
    }

    void update(size_t index, M value) {
        index += base_data_size;
        data[index] = value;
        while (index >>= 1) {
            data[index] = merge(data[2 * index], data[2 * index + 1]);
        }
    }

    // [left, right)
    M query(size_t left_index, size_t right_index) {
        M left = identity_element, right = identity_element;
        left_index += base_data_size;
        right_index += base_data_size;
        while (left_index < right_index) {
            if (left_index & 1) left = merge(left, data[left_index++]);
            if (right_index & 1) right = merge(data[--right_index], right);
            left_index >>= 1;
            right_index >>= 1;
        }
        return merge(left, right);
    }

    const M &operator[](const size_t index) {
        return data[index + base_data_size];
    }
};

int main() {
    int N;
    cin >> N;
    vector<pair<int, ll>> input(N);
    for (int i = 0; i < N; i++) cin >> input[i].first;
    for (int i = 0; i < N; i++) cin >> input[i].second;
    auto merge = [](ll a, ll b) {
        return max(a, b);
    };
    SegmentTree<ll> tree(N + 1, merge, 0);
    vector<ll> dp(N, 0);
    for (int i = 0; i < N; i++) {
        ll before = tree.query(0, input[i].first);
        dp[i] = before + input[i].second;
        tree.update(input[i].first, dp[i]);
    }
    ll ans = 0;
    for (int i = 0; i < N; i++) {
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;
}


Measured memory_bytes: 9088
#include <bits/stdc++.h>
using namespace std;
int main(){
  vector<vector<int>> c(3,vector<int>(3));
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      cin >> c[i][j];
    }
  }
  string ans="Yes";
  for(int i=0;i<2;i++){
    for(int j=0;j<2;j++){
      if(c[i][j]-c[i+1][j]!=c[i][j+1]-c[i+1][j+1]){
        ans="No";
        break;
      }
      if(c[i][j]-c[i][j+1]!=c[i+1][j]-c[i+1][j+1]){
        ans="No";
        break;
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    X, t = list(map(int,_in[0].split(' ')))  # type:list(int)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    cnt = max(X-t,0)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


Measured memory_bytes: 38256
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = (s); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for(int i = (n); i >= 0; i--)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << '\n';
#define CFYN(n) cout << ( (n) ? "YES":"NO") << '\n';
#define OUT(n) cout << (n) << '\n';
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int main(void)
{
    IOS
    string s; cin >> s;
    stack<char> st;
    int ans = 0;
    REP(i,s.size()) {
        if (st.size() != 0 && st.top() != s[i]) {
            st.pop();
            ans+=2;
        } else st.push(s[i]);
    }

    OUT(ans)

    return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
int main(){
    ll n,k,A[200001];
    cin>>n>>k;
    rep(i,n) cin>>A[i];
    ll sum=0;
    rep(i,n) sum+=A[i];
    vector<ll> B;
    ll a=sum;
    for(int i=1;i<=sqrt(sum);i++)if(sum%i==0){
        B.push_back(i);
        B.push_back(sum/i);
    }
    sort(B.begin(),B.end());
    ll ans=0;
    for(auto i:B){
        ll mod=i,x=0,y=0,C[505];
        rep(j,n) C[j]=A[j]%mod;
        rep(j,n) x+=C[j];
        sort(C,C+n,greater<int>());
        rep(j,x/mod) C[j]-=mod;
        rep(j,n) y+=abs(C[j]);
        if(y/2<=k) ans=i;
    }
    cout<<ans;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args)
	{
		Scanner stdIn = new Scanner(System.in);
		
	
		int a = stdIn.nextInt();
		int b = stdIn.nextInt();
		int c = stdIn.nextInt();
		
		int count = 0;
		
		for(int i=a;i<=b;i++)
		{
			if(c%i==0)
			{
				count++;
			}
		}
		System.out.println(count);
	}

}

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

template<typename T, typename Q>
istream &operator>>(istream &is, pair<T, Q> &p) {
	return is >> p.first >> p.second;
}

template<typename T>
istream &operator>>(istream &is, vector<T> &v) {
	for (auto &x : v) is >> x;
	return is;
}

template<typename T, typename Q>
ostream &operator<<(ostream &os, pair<T, Q> p) {
	return os << "(" << p.first << ", " << p.second << ")";
}

template<typename T>
ostream &operator<<(ostream &os, vector<T> v) {
	os << "[";
	for (auto it = v.begin(); it != v.end(); it++)
		os << (it == v.begin() ? "" : ", ") << *it;
	return os << "]";
}

template<typename T, typename Q>
ostream &operator<<(ostream &os, map<T, Q> m) {
	os << "[";
	for (auto it = m.begin(); it != m.end(); it++) 
		os << (it == m.begin() ? "" : ", ") << *it;
	return os;
}
#define imie(...) " [" << #__VA_ARGS__": " << (__VA_ARGS__) << "] "
#define int long long

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; cin >> n;
	vector<pair<int, int>> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i].second >> a[i].first;
	}
	int sum = 0;
	sort(a.begin(), a.end());
	cerr << imie(a) << '\n';
	for (int i = 0; i < n; i++) {
		sum += a[i].second;
		if (sum > a[i].first) {
			cerr << imie(i) << '\n';
			cout << "No\n";
			return 0;
		}
	}
	cout << "Yes\n";
}


















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

int main()
{
    int n,i,flg=0;
    cin>>n;

    for(i=1;i<10;i++)
    {
        if(n % i == 0 && n / i < 10)
        {
            flg++;
            break;
        }
    }
  
  if(flg == 1) cout<<"Yes";
  else cout<<"No";
}

Measured memory_bytes: 3660
n = int(input())
heights = list(map(int, input().split()))
cnt = 0
for i in range(1,n):
  if heights[i] >= heights[i-1]:
    pass
  else:
    x = heights[i-1] - heights[i]
    cnt += x
    heights[i] = heights[i-1]
    
print(cnt)

Measured memory_bytes: 32172
#include <algorithm>
#include <bitset>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
using namespace std;

#define ABS(a) (((a) >= 0) ? (a) : -(a))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) > (b) ? (b) : (a))
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define RFOR(i, a, b) for (int i = a; i > b; --i)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define int long long

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

int A, B, C;
string ans;

signed main() {
  cin >> A >> B >> C;

  if (A+B >= C) {
    ans = "Yes";
  } else {
    ans = "No";
  }

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


Measured memory_bytes: 256
from collections import Counter
N = int(input())
B = [int(x) for x in input().split()]
A=Counter(B)
V, C = zip(*A.most_common())
count=0
for x in C:
  if x==0:
    break
  count+=x*(x-1)/2
for x in B:
  ans=count-A[x]+1
  print(int(ans))


Measured memory_bytes: 36892
H, W = map(int, input().split())


a = int(W / 2 + 0.5)

if H == 1 or W == 1:
    print(1)
    exit()

if H % 2 == 0:
    print(W * H // 2)
else:
    print(W * (H -1) // 2 + a)


Measured memory_bytes: 2940
import sys

def solve():
    n, q = map(int, sys.stdin.readline().split())
    uf = UnionFind(n)

    for lp in range(q):
        c, x, y = map(int, sys.stdin.readline().split())

        if c == 0:
            uf.unite(x, y)
        else:
            print(1 if uf.same(x, y) else 0)


class UnionFind:

    def __init__(self, n):
        self.ds = [i for i in range(n)]
        self.root = [i for i in range(n)]
        self.rank = [0] * n

    def find_root(self, x):
        if x != self.root[x]:
            self.root[x] = self.find_root(self.root[x])

        return self.root[x]

    def same(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def unite(self, x, y):
        p = self.find_root(x)
        q = self.find_root(y)

        if p == q:
            return None

        if self.rank[p] < self.rank[q]:
            self.root[p] = q
        elif self.rank[q] < self.rank[p]:
            self.root[q] = p
        else:
            self.root[q] = p
            self.rank[p] += 1

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()

Measured memory_bytes: 9192
/*
貪欲
後ろから見る
DP
順位表をチェック
二分探索


*/
#pragma GCC optimize("Ofast")
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
#include <cmath>
#include <limits>
#include <iostream>
#include <map>
#include<tuple>
using namespace std;
#define INF 3e18+7
#define MAX 100000
#define MOD 1000000007
typedef long long ll;
typedef pair<ll,ll> P;
//typedef pair<pair<int,int>,int> p;
#define bit(n,k) ((n>>k)&1) /*nのk bit目*/
#define rad_to_deg(rad) (((rad)/2/M_PI)*360)
struct edge{ll to,cost,val;};
template<class T,class U>bool chmin(T&a,const U&b){if(a<=b)return false;a=b;return true;}
template<class T,class U>bool chmax(T&a,const U&b){if(a>=b)return false;a=b;return true;}
//__builtin_popcount(S);
//C.erase(unique(C.begin(),C.end()),C.end());

int S[110000],Z[110000];


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

    int N,M,X;
    cin>>N>>M;

    vector<int> V[110000];
    for(int i=0;i<N;i++){
        cin>>X;
        V[X%M].push_back(X);
    }
    for(int i=0;i<M;i++){
        sort(V[i].begin(),V[i].end());
        S[i]=(int)V[i].size();
        int count=1;
        for(int j=0;j<S[i]-1;j++){
            if(V[i][j]==V[i][j+1]) count++;
            else{
                Z[i]+=count-count%2;
                count=1;
            }
        }
        Z[i]+=count-count%2;
    }
    int count=0;
    for(int i=0;i<=M/2;i++){
        if(i==0 || i*2==M){
            count+=S[i]/2;
            continue;
        }

        count+=min(S[i],S[M-i]);
        if(S[i]>S[M-i]){
            S[i]-=S[M-i];
            count+=min(Z[i],S[i])/2;
        }else{
            S[M-i]-=S[i];
            count+=min(Z[M-i],S[M-i])/2;
        }
    }
    cout<<count<<endl;

}

Measured memory_bytes: 6784
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define fi first
#define se second
#define PI (acos(-1))

template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){
	int len=d.size();
	rep(i,len){
		s<<d[i];if(i<len-1) s<<" ";
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){
	int len=d.size();
	rep(i,len){
		s<<d[i]<<endl;
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){
	s<<"{ ";
	for(auto itr=v.begin();itr!=v.end();++itr) {
		if (itr!=v.begin()) {s<< ", ";}
		s<<(*itr);
	}
	s<<" }";
	return s;
}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){
	s<<"{"<<endl;
	for(auto itr=m.begin();itr!=m.end();++itr){
		s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;
	}
	s<<"}"<<endl;
	return s;
}

const ll mod=1e9+7;
const ll inf=1e15;
const int INF=1e9;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int q;
	cin>>q;
	priority_queue<ll> que1;
	priority_queue<ll,vector<ll>,greater<ll>> que2;
	ll cons=0;
	ll suml=0,sumr=0;
	while(q--){
		int c;
		cin>>c;
		if(c==1){
			ll a,b;
			cin>>a>>b;
			cons+=b;
			if(que1.size()>que2.size()){
				ll top=que1.top();
				if(top<=a){
					que2.push(a);
					sumr+=a;
				}else{
					que2.push(top);
					sumr+=top;
					suml-=top;
					que1.pop();
					que1.push(a);
					suml+=a;
				}
			}else{
				if(que1.empty()){
					que1.push(a);
					suml+=a;
				}else{
					ll top=que2.top();
					if(a<=top){
						que1.push(a);
						suml+=a;
					}else{
						que1.push(top);
						suml+=top;
						sumr-=top;
						que2.pop();
						que2.push(a);
						sumr+=a;
					}
				}
			}
		}else{
			ll now=que1.top();
			cout<<now<<endl;
			ll ans=now*(ll)que1.size()-suml;
			ans+=sumr-now*(ll)que2.size()+cons;
			cout<<ans<<endl;
		}
	}
}

Measured memory_bytes: 3828
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007
typedef unsigned long long ull;
typedef   signed long long sll;


#define N_MAX 100
#define M_MAX 100

ull n;
int a[N_MAX];

void swap_adj(ull *a, ull *b){
	ull tmp = *b;
	*b = *a;
	*a = tmp;
	return;
}

int comp(const void *a, const void *b){
	if (*(ull*)a > *(ull*)b) {
		return -1;
	} else if (*(ull*)a < *(ull*)b) {
		return +1;
	} else {
		return 0;
	}
}

int solve(){
	
	int i;
	int b[8] = {0, 0, 0, 0, 0, 0, 0, 0}; // = {0};]
	int tourist = 0, izryt = 0;

	for (i = 0; i < n; i++) {
		if (a[i] >= 3200) {
			tourist++;
		} else {
			b[a[i] / 400]++;
		}
	}

	for (i = 0; i < 8; i++) {
		if (b[i]) izryt++;
	}

	// if (izryt == 0) izryt = 1; // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

	printf("%d %d\n", (izryt ? izryt : 1), izryt + tourist);

	return 0;
}

int main(void){
	ull i;

	scanf("%llu", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}

	solve();

	return 0;
}


Measured memory_bytes: 128
n=int(input())
A=input().split()
B=input().split()
C=input().split()
for i in range(n):
    A[i]=int(A[i])
    B[i]=int(B[i])
    C[i]=int(C[i])
C.sort()
C=C[::-1]
B.sort()
B=B[::-1]
A.sort()
A=A[::-1]


Cres=[1 for i in range(n)]
Bres=[0 for i in range(n)]
Ares=[0 for i in range(n)]

k=-1
for i in range(n):
    currsize=B[i]
    while k+1<n and currsize<C[k+1]:
        k+=1
    Bres[i]=k+1

k=-1
su=0
for i in range(n):
    currsize=A[i]
    while k+1<n and currsize<B[k+1]:
        k+=1
        su+=Bres[k]
    Ares[i]=su

su=0
for i in range(n):
    su+=Ares[i]
print (su)



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

#define int long long

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

#define all(box) box.begin(), box.end()

using namespace std;

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

const long long INF = LLONG_MAX/3;

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

struct UnionFind{
	std::vector<int> par,siz;
	void init(int n){
		par.resize(n);
		for(int i=0;i<n;i++)par[i]=i;
		siz.resize(n,1);
	}
	UnionFind(int n){
		init(n);
	}
	int root(int n){
		if(par[n]==n)return n;
		else return par[n]=root(par[n]);
	}
	bool issame(int x,int y){
		return (root(x)==root(y));
	}
	bool marge(int a,int b){
		if(issame(a,b))return false;
		else{
			a=root(a),b=root(b);
			if(siz[a]<siz[b])swap(a,b);
			siz[a]+=siz[b];
			par[a]=par[b];
			return true;
		}
	}
	int size(int n){
		return siz[root(n)];
	}
};

long long gcd(long long a,long long b){
    if(b==0)return a;
    return gcd(b,a%b);
}
long long lcm(long long i,long long j){
    return i*(j/gcd(i,j));
}

const int MOD=1e9+7;
long long fac[510000], finv[510000], inv[510000];
long long MAX=510000;
bool COMinited=false;
long long COM(int n, int k){
	if(COMinited==false){
		fac[0] = fac[1] = 1;
    	finv[0] = finv[1] = 1;
    	inv[1] = 1;
    	for (int i = 2; i < MAX; i++){
        	fac[i] = fac[i - 1] * i % MOD;
        	inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        	finv[i] = finv[i - 1] * inv[i] % MOD;
    	}
		COMinited=true;
	}
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
long long modinv(long long a, long long mod) {
    return modpow(a, mod - 2, mod);
}
signed main(){
	int a[3][3];
	rep(i,3){
		rep(j,3){
			cin>>a[i][j];
		}
	}
	int n;
	cin>>n;
	bool b[3][3]={};
	rep(i,n){
		int t;
		cin>>t;
		rep(j,3){
			rep(k,3){
				if(a[j][k]==t)b[j][k]=true;
			}
		}
	}
	bool re=false;
	rep(i,3){
		bool t=true;
		rep(j,3){
			if(b[i][j]==false)t=false;
		}
		if(t)re=true;
	}
	rep(i,3){
		bool t=true;
		rep(j,3){
			if(b[j][i]==false)t=false;
		}
		if(t)re=true;
	}
	if((b[0][0]&&b[1][1]&&b[2][2])||(b[2][0]&&b[1][1]&&b[0][2]))re=true;
	if(re)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}

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

#define rep(i,n) for( (i)=0;(i)<(n);++(i) )
#define repr(i,n) for( (i)=(n);(i)>0;==(i) )
#define FOR(i,j,n) for( (i)=(j);(i)<(n);++(i) )
#define forr(i,j,n) for( (i)=(j);(i)>(n);--(i) )
#define debg(a) cout<<(a)<<endl;
#define INF 9999999
#define Int long long 
int i,j,k;
int dx,dy;
int a,b,c;
string s,t;

int main(){ 
  int candy[3];
  cin>>candy[0]>>candy[1]>>candy[2];
  sort(candy,candy+3);
  cout<<( (candy[2]==candy[0]+candy[1]?"Yes":"No") )<<endl;


  return 0;
}


Measured memory_bytes: 256