akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = ll(1e12);
const ll mod = 998244353;
const double pi = acos(-1);
#define rep0(i,n) for(ll (i) = 0; (i) < (n); ++(i))
#define rrep0(i,n) for(ll (i) = (n) - 1; (i) >= 0; --(i))
#define rep1(i,n) for(ll (i) = 1; (i) <= (n); ++(i))
#define rrep1(i,n) for(ll (i) = (n); (i) >= 1; --(i))
#define nfor(i,a,b) for(ll (i) = (a); (i) < (b); ++(i))
#define pf(x) cout << (x) << endl
#define all(x) (x).begin(),(x).end()
#define yes pf("Yes")
#define no pf("No")

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

ll lcm(ll a,ll b){
    ll g = gcd(a,b);
    return a / g * b;
}

ll factorial(ll n){
    ll t = 1;
    rep1(i, n){
        t *= i;
        t %= mod;
    }
    return t;
}

ll power(ll a, ll b){
    ll ret = 1 % mod;
    a %= mod;
    while(b) {
        if(b & 1LL) ret = ret * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ret;
}

vector<ll> inv, FactorialInv, Factorial;

void init_combination(ll MAX){
    Factorial.resize(MAX + 1);
    FactorialInv.resize(MAX + 1);
    inv.resize(MAX + 1);
    Factorial[0] = 1;
    inv[0] = 1;
    for(int i = 1; i <= MAX; i++){
        Factorial[i] = Factorial[i - 1] * i % mod;
    }
    FactorialInv[MAX] = power(Factorial[MAX], mod - 2);
    for(ll i = MAX - 1; i >= 0; i--) {
        FactorialInv[i] = FactorialInv[i+1] * (i+1) % mod;
    }
    for(int i = 1; i <= MAX; i++) {
        inv[i] = FactorialInv[i] * Factorial[i-1] % mod;
    }
}

ll combination(ll a, ll b){
    if((a == b) || (b == 0)){
        return 1;
    }
    if(a < b) return 0;
    if(b < 0) return 0;
    ll ans = Factorial[a] * FactorialInv[b] % mod;
    ans = ans * FactorialInv[a - b] % mod;
    return ans;
}

int main(){
    ll n,m,k,ans = 0;
    init_combination(1e6);
    cin >> n >> m >> k;
    rep0(i, k + 1){
        ll cnt = m;
        cnt *= power(m - 1, n - i - 1);
        cnt %= mod;
        cnt *= combination(n - 1,i);
        cnt %= mod;
        ans += cnt;
        ans %= mod;
    }
    pf(ans);
    return 0;
}


Measured memory_bytes: 26616
N, M = map(int, input().split())

l = []

for i in range(N):
    A = [int(x) for x in input().split()]

    for j in range(1, A[0] + 1):
        l.append(A[j])

ans = 0

for i in range(M + 1):
    if l.count(i) == N:
        ans += 1

print(ans)


Measured memory_bytes: 3060
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

#define MAX_DIMENS 100

double calc_manhattan_dist(int n, int x[], int y[]);
double calc_euclid_dist(int n, int x[], int y[]);
double calc_p3_dist(int n, int x[], int y[]);
double calc_chebyshev_dist(int n, int x[], int y[]);

int main(void)
{
    int i;

    int num_dimens;
    scanf("%d", &num_dimens);

    int x[MAX_DIMENS], y[MAX_DIMENS];
    for (i = 0; i < num_dimens; i++) {
        scanf("%d", &x[i]);
    }
    for (i = 0; i < num_dimens; i++) {
        scanf("%d", &y[i]);
    }

    double manhattan_dist = calc_manhattan_dist(num_dimens, x, y);
    double euclid_dist = calc_euclid_dist(num_dimens, x, y);
    double p3_dist = calc_p3_dist(num_dimens, x, y);
    double chebyshev_dist = calc_chebyshev_dist(num_dimens, x, y);

    printf("%f\n%f\n%f\n%f\n",
            manhattan_dist, euclid_dist, p3_dist, chebyshev_dist);

    return 0;
}

double calc_manhattan_dist(int n, int x[], int y[])
{
    int i;

    double dist = 0;
    for (i = 0; i < n; i++) {
        dist += abs(x[i] - y[i]);
    }

    return dist;
}

double calc_euclid_dist(int n, int x[], int y[])
{
    int i;

    double dist_sq = 0;
    for (i = 0; i < n; i++) {
        dist_sq += pow(x[i] - y[i], 2);
    }
    double dist = sqrt(dist_sq);

    return dist;
}

double calc_p3_dist(int n, int x[], int y[])
{
    int i;

    double dist_cb = 0;
    for (i = 0; i < n; i++) {
        dist_cb += pow(abs(x[i] - y[i]), 3);
    }
    double dist = cbrt(dist_cb);

    return dist;
}

double calc_chebyshev_dist(int n, int x[], int y[])
{
    int i;

    double max = abs(x[0] - y[0]);
    for (i = 1; i < n; i++) {
        int dist_i = abs(x[i] - y[i]);
        if (dist_i > max) {
            max = dist_i;
        }
    }

    return max;
}

Measured memory_bytes: 708
s=input()
t=list(map(int,input().split()))
list=[]
a=int(s)
for j in range(a):
  list.append(t[j])
list.sort()
c=0
for i in range(a):
  if t[i]!=list[i]:
    c = c-1
if c<-2:
  print('NO')
else:
  print('YES')

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <cstring>
#include <utility>
#include <map>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;


int main()
{
    ll n,k,q;
    cin>>n>>k>>q;
    vector<int> a(q);
    
    vector<int> p(n);
    for(int i=0;i<n;i++)
        p[i]=0;
    for(int i=0;i<q;i++)
    {cin>>a[i];
        p[a[i]-1]++;
    }
    int c=k-q;
    for(int i=0;i<n;i++)
    {
        if(p[i]+c>0)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
        
    }
    return 0;
}



Measured memory_bytes: 1408
using System;
using System.Collections.Generic;
using System.Linq;
class ilds1_2_b{
  public static void Main(){
    int n = int.Parse(Console.ReadLine());
    int[] num = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
    int minj;
    int count = 0;
    for(int i=0; i<n; i++){
      minj = i;
      for(int j=i; j<n; j++){
        if(num[j] < num[minj]){
          minj = j;
        }
      }
      if(i != minj){
        int temp = num[i];
        num[i] = num[minj];
        num[minj] = temp;
        count++;
      }
    }
    for(int i=0; i<n; i++){
      if(i == n-1){
        Console.WriteLine(num[i]);
      }
      else{
        Console.Write("{0} ",num[i]);
      }
    }
    Console.WriteLine(count);
  }
}



Measured memory_bytes: 18388
#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<map>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<set>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
#define INF 1000000100
#define rep(i,n) for (int i=0;i<n;i++)


int main(){
    int N;
    cin >> N;
    int a[N], b[N], c[N-1];
    rep(i,N) cin >> a[i];
    rep(i,N) cin >> b[i];
    rep(i,N-1) cin >> c[i];
    int sum=0;
    rep(i,N){
        sum += b[i];
        if(i>0 && a[i]==a[i-1]+1){
            sum+=c[a[i-1]-1];
        }
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 3164
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
#include<string>
#include<iostream>
#include<set>
#include<map>
#include<deque>
using namespace std;
typedef long long ll;
typedef pair<ll, ll>pii;
typedef pair<pii, ll>pi3;
ll mod = 1000000007;
int main()
{
	string s;
	cin >> s;
	//cout << min(min(a + b, b + c), c + a) << endl;
	printf((s[0]=='9'||s[1]=='9') ? "Yes\n" : "No\n");
}

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

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

const int M = 1000005;

int main() {
  int n;
  cin >> n;
  vector<int> as(n);
  rep(i, n) cin >> as[i];
  vector<int> cnt(M);
  for (int x : as) {
    if (cnt[x] != 0) {
      cnt[x] = 2;
      continue;
    }
    for (int i = x; i < M; i += x) cnt[i]++;
  }
  int ans = 0;
  for (int x : as) {
    if (cnt[x] == 1) ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 7968
#include<cstdio>
#include<iostream>

using namespace std;

#define N 100001 

int a[N];
long long cnt[N<<1];

void read(int &x)
{
	x=0; char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}

int main()
{
	int n,m;
	read(n); read(m);
	for(int i=1;i<=n;++i) read(a[i]);
	int l,r;
	long long tot=0;
	for(int i=1;i<n;++i)
	{
		l=a[i];
		r=a[i+1];
		if(l>r) r+=m;
		tot+=r-l;
		if(r-l>1)
		{
			cnt[l+2]++; 
			cnt[r+1]-=r-(l+2)+2;
			cnt[r+2]+=r-(l+2)+1;
		}
	}
	for(int i=1;i<=m*2;++i) cnt[i]+=cnt[i-1];
	for(int i=1;i<=m*2;++i) cnt[i]+=cnt[i-1];
	long long ans=tot;
	for(int i=1;i<=m;++i) ans=min(ans,tot-cnt[i]-cnt[i+m]);
	cout<<ans;
}

Measured memory_bytes: 2176
// AOJ 2027: Reading a Chord
// 2017.12.11 bal4u@uu

#include <stdio.h>
#include <string.h>

char tones[12][3] = {"C","C#","D","D#","E","F","F#","G","G#","A","A#","B"};
char base[5][3] = {"","7","M7","m","m7"};
char tension[12][4] = {"","-9","9","+9","-11","11","+11","","-13","13","+13"};
char tr['G'+1]['#'+1];
char f[12], t[12];
char ans[100][10]; int sz;
char tbl[5][4] = {{4,7},{4,7,10},{4,7,11},{3,7},{3,7,10}};

int main()
{
	int cno, m, i, a, b, u, v;
	char buf[5];

	tr['C'][0] = 0, tr['C']['#'] = 1, tr['D'][0] = 2, tr['D']['#'] = 3;
	tr['E'][0] = 4, tr['F'][0] = 5, tr['F']['#'] = 6;
	tr['G'][0] = 7, tr['G']['#'] = 8, tr['A'][0] = 9, tr['A']['#'] = 10;
    tr['B'][0] = 11;

	scanf("%d", &cno);
	while (cno--) {
		scanf("%d", &m);
		memset(f, 0, sizeof(f));
		while (m--) {
			scanf("%s", buf);
			if (buf[1] != '#') buf[1] = 0;
			f[tr[buf[0]][buf[1]]] = 1;
		}

		sz = 0;
		for (a = 0; a < 12; a++) for (b = 0; b < 5; b++) {
			memset(t, 0, sizeof(t));
			t[a] = 1;
			for (i = 0; tbl[b][i]; i++) t[(a+tbl[b][i])%12] = 1;

			if (!memcmp(f, t, sizeof(f))) {
				sprintf(ans[sz++], "%s%s", tones[a], base[b]);
				continue;
			}

			for (i = 1; i <= 10; i++) {
				if (i == 7) continue;
				u = (a+i)%12;
				v = t[u], t[u] = 1;
				if (!memcmp(f, t, sizeof(f)))
					sprintf(ans[sz++], "%s%s(%s)", tones[a], base[b], tension[i]);
				t[u] = v;
			}

			t[(a+7)%12] = 0, t[(a+18)%12] = 1;
			if (!memcmp(f, t, sizeof(f)))
				sprintf(ans[sz++], "%s%s(-5)", tones[a], base[b]);

			t[(a+18)%12] = 0; t[(a+8)%12] = 1;
			if (!memcmp(f, t, sizeof(f)))
				sprintf(ans[sz++], "%s%s(+5)", tones[a], base[b]);
		}

		if (!sz) puts("UNKNOWN");
		else {
			printf(ans[0]);
			for (i = 1; i < sz; i++) putchar(' '), printf(ans[i]);
			putchar('\n');
		}
	}
	return 0;
}

Measured memory_bytes: 1748
#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

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

const ll MAX=1<<18;
const ll INF=0x3f3f3f3f;
ll n,h[MAX],a,b;
ll bin(ll x,ll y){
    if(y-x==1) return x;
    ll p=(x+y)/2,t=0;
    for(ll i=0;i<n;i++) if(h[i]>b*p){
        t+=(h[i]-b*p+(a-b)-1)/(a-b);
    }
    if(t>p) return bin(p,y);
    return bin(x,p);
}
int main(){
    scanf("%lld%lld%lld",&n,&a,&b);
    for(ll i=0;i<n;i++) scanf("%lld",&h[i]);
    printf("%lld\n",bin(0,1e9+7)+1);
    return 0;
}


Measured memory_bytes: 1024
#include <algorithm>
#include <cmath>
#include <functional>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <climits>

using namespace std;
using ll  = long long;
template <typename T> T In() {
    T t;
    cin >> t;
    return t;
}
template <typename T> vector<T> ReadVec1(int N) {
    vector<T> vec(N);
    for(int i = 0; i < N; i++)
        vec[i] = In<T>();
    return move(vec);
}
template <typename T> vector<vector<T>> Vec2(int i, int j, T ini = 0) {
    vector<vector<T>> vec(i, vector<T>(j, ini));
    return move(vec);
}
template <typename T> vector<vector<vector<T>>> Vec3(int i, int j, int k, T ini = 0) {
    vector<vector<vector<T>>> vec(i, vector<vector<T>>(j, vector<T>(k, ini)));
    return move(vec);
}

int main() {
    int N = In<int>(), W = In<int>();
    vector<int> ws(N), vs(N);
    for(int n = 0; n < N; n++){
        ws[n] = In<int>();
        vs[n] = In<int>();
    }
    auto dp = Vec2<ll>(N+1, W + 1);
    for(int n = 0; n < N; n++){
        for(int w = 1; w <= W; w++){
            if(w - ws[n]>=0){
                dp[n + 1][w] = max(dp[n][w], dp[n][w - ws[n]] + vs[n]);
            } else {
                dp[n + 1][w] = dp[n][w];
            }
        }
    }
    cout << dp[N][W] << endl;
}

Measured memory_bytes: 80256
def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    a = read_int()
    b = read_int()
    h = read_int()
    return (a+b)*h//2


if __name__ == '__main__':
    print(solve())


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

using namespace std;
typedef long long ll;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mp make_pair
#define pb push_back
#define lp(i,s,f) for(ll i = s; i < ll(f); i++)
#define inF freopen("input.in", "r", stdin);
#define outF freopen("output.in", "w", stdout);
#define endl '\n'
#define MOD 1000000007
#define mm(arr) memset(arr, 0, sizeof(arr))
#define int ll

int32_t main(){
    FAST
    int t = 1;
    while(t--){
        int n;
        cin >> n;
        int arr[n];
        for(int i = 0; i < n; i++){
            cin >> arr[i];
        }
        sort(arr, arr + n);
        reverse(arr, arr + n);
        int ans = arr[0];
        int cnt = 1;
        for(int i = 1; i < n; i++){
            if(cnt == n - 1)break;
            ans += arr[i];
            cnt++;
            if(cnt == n - 1)break;
            ans += arr[i];
            cnt++;
        }
        cout << ans << endl;
    }
    return 0;
}


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

int main(){
   int A, B;
   cin >> A >> B;
   int cnt = 0;
   for (int i=A; i<=B; i++){
      string str = to_string(i);
      string str_f = str.substr(0, 2);
      string str_r = str.substr(3, 2);
      reverse(str_r.begin(), str_r.end());
      if (str_f == str_r){
         cnt++;
      }
   }
   cout << cnt << endl;
}



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>
using namespace std;
int main(){
int cou = 0;
int a,b,c;
cin >> a >> b >> c;
bool ok = true;
if(a > c)ok = false;
if(a+b < c)ok = false;
if(ok)cout << "YES" << endl;
else cout << "NO" << endl;

        return 0;
}

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

int main()
{
	int n, m;
	cin >> n >> m;
	const int MAX = 50;
	int a[MAX], b[MAX];
	for (int i = 0; i < m; i++) {
		cin >> a[i] >> b[i];
	}
	int road[MAX];
	for (int i = 0; i < n; i++) {
		road[i] = 0;
	}
	for (int i = 0; i < m; i++) {
		road[a[i] - 1] += 1;
		road[b[i] - 1] += 1;
	}
	for (int j = 0; j < n; j++) {
		cout << road[j] << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <cstdlib>
#include <random>
#include <map>
#include <string>
#include <algorithm>
#include <bitset>
#include <numeric>
#include <cassert>
#include <iomanip>
#include <cmath>

using namespace std;

typedef long long ll;
typedef long double ld;

const int M = (int)1e5 + 1;
const ld EPS = 1e-9;
const ll MOD = (ll)1e9 + 7;
const ll MAX = 1000 * 1000 * 1000;
const ll INF = (ll)1e9 + 10;
const ld PI = acosl(-1);
const int N = (int)1e6 + 2;

int d[N];
bool used[N];

struct Edge {
	int v, u, w, idx;
};

vector<Edge> g[N];
int answer[N];
int color[N];

void solve() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> d[i];
	}

	for (int i = 0; i < m; i++) {
		int v, u;
		cin >> v >> u;
		v--, u--;
		g[v].push_back({ v, u, 0, i });
		g[u].push_back({ u, v, 0, i });
	}

	set<pair<int, int>> vs;
	for (int i = 0; i < n; i++) {
		vs.insert({ d[i], i });
	}

	while (!vs.empty()) {
		auto tmp = *vs.begin();
		int v = tmp.second;
		vs.erase(vs.begin());
		if (used[v]) {
			continue;
		}
		bool fnd = false;
		for (auto& e : g[v]) {
			int u = e.u;
			if (used[u]) {
				fnd = true;
				color[v] = 3 - color[u];
				answer[e.idx] = d[v];
				break;
			}
		}

		if (fnd) {
			used[v] = true;
			continue;
		}

		for (auto& e : g[v]) {
			int u = e.u;
			if (d[u] == d[v]) {
				color[v] = 1;
				color[u] = 2;
				fnd = true;
				answer[e.idx] = d[v];
				used[v] = used[u] = true;
			}
		}

		if (!fnd) {
			cout << -1 << endl;
			return;
		}
	}

	string colors;
	for (int i = 0; i < n; i++) {
		if (color[i] == 1) {
			colors += 'W';
		}
		else {
			assert(color[i] == 2);
			colors += 'B';
		}
	}
	cout << colors << endl;

	for (int i = 0; i < m; i++) {
		if (answer[i] == 0) {
			cout << MAX << "\n";
		}
		else {
			cout << answer[i] << "\n";
		}
	}
	cout << endl;
}

int main() {
	//auto trash = freopen("a.in", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

Measured memory_bytes: 45568
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		String s = sc.next();
		//		int[] a = new int[n];

		//		int sum = 0;
		//		for (int i = 0; i < n; i++) {
		//			a[i] += sc.nextInt();
		//		}

		int min = Integer.MAX_VALUE;

		//　TLEしちゃう
		//		for (int i = 0; i < n; i++) {
		//			int count = 0;
		//			for (int j = 0; j < n; j++) {
		//				if (i == j) {
		//					continue;
		//				}
		//				if (j < i) {
		//					if (s.charAt(j) == 'W') {
		//						count++;
		//					}
		//				}
		//				if (j > i) {
		//					if (s.charAt(j) == 'E') {
		//						count++;
		//					}
		//				}
		//			}
		//			min = Math.min(min, count);
		//		}
		int[] w = new int[n + 2];
		int[] e = new int[n + 2];

		int count = 0;
		for (int i = 1; i <= n; i++) {
			if (s.charAt(i - 1) == 'W') {
				count++;

			}
			w[i] = count;
		}
		count = 0;
		for (int i = n; i > 0; i--) {
			if (s.charAt(i - 1) == 'E') {
				count++;
			}
			e[i] = count;
		}

		int tmp = 0;
		for (int i = 1; i <= n; i++) {
			tmp = w[i - 1] + e[i + 1];
			min = Math.min(min, tmp);
		}

		System.out.println(min);

		sc.close();
	}
}

Measured memory_bytes: 32144
import java.util.Scanner;
class Main
{
    public static void main(String args[])
    {
	Scanner scan=new Scanner(System.in);
	while(true)
	    {
	int n,m;
	n=scan.nextInt();
	m=scan.nextInt();
	if(n==0 && m==0)break;
	int p[]=new int[n];
	for(int i=0;i<n;i++)
	    {
		p[i]=scan.nextInt();
	    }
	for(int i=0;i<n-1;i++)
	    {
		for(int j=n-1;j>i;j--)
		    {
			if(p[j]>p[j-1])
			    {
				int t=p[j-1];
				p[j-1]=p[j];
				p[j]=t;
			    }
		    }
	    }
	
	int sum=0;
	int j=0;
for(int i=1;i<=n;i++)
	    {
		if(i%m!=0)sum+=p[i-1];
		
	    }
System.out.println(sum);

	    }
    }
}

Measured memory_bytes: 52584
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
int PREP = (cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(9), 0);
//int SEGV = getenv("D") || (exit(system("D= SEGFAULT_SIGNALS=all catchsegv ./prog.exe") >> 8), 0);
const int DX[4] = { 0, 0, +1, -1 };
const int DY[4] = { +1, -1, 0, 0 };
int main() {
    int N, M; cin >> N >> M;
    vector<Int> A(N), B(N), C(N), D(M), E(M), F(M);
    vector<Int> X, Y;
    X.push_back(0);
    Y.push_back(0);
    for (int i = 0; i < N; i++) {
        cin >> A[i] >> B[i] >> C[i];
        X.push_back(A[i]);
        X.push_back(B[i]);
        Y.push_back(C[i]);
    }
    for (int i = 0; i < M; i++) {
        cin >> D[i] >> E[i] >> F[i];
        X.push_back(D[i]);
        Y.push_back(E[i]);
        Y.push_back(F[i]);
    }
    sort(begin(X), end(X));
    X.erase(unique(begin(X), end(X)), end(X));
    sort(begin(Y), end(Y));
    Y.erase(unique(begin(Y), end(Y)), end(Y));
    int zero_x = 2 * (lower_bound(begin(X), end(X), 0) - begin(X));
    int zero_y = 2 * (lower_bound(begin(Y), end(Y), 0) - begin(Y));
    for (int i = 0; i < N; i++) {
        A[i] = 2 * (lower_bound(begin(X), end(X), A[i]) - begin(X));
        B[i] = 2 * (lower_bound(begin(X), end(X), B[i]) - begin(X));
        C[i] = 2 * (lower_bound(begin(Y), end(Y), C[i]) - begin(Y));
    }
    for (int i = 0; i < M; i++) {
        D[i] = 2 * (lower_bound(begin(X), end(X), D[i]) - begin(X));
        E[i] = 2 * (lower_bound(begin(Y), end(Y), E[i]) - begin(Y));
        F[i] = 2 * (lower_bound(begin(Y), end(Y), F[i]) - begin(Y));
    }
    vector<vector<char>> visited(X.size() * 2 + 1, vector<char>(Y.size() * 2 + 1));
    for (int i = 0; i < N; i++) {
        for (int x = A[i]; x <= B[i]; x++) {
            visited[x][C[i]] = 1;
        }
    }
    for (int i = 0; i < M; i++) {
        for (int y = E[i]; y <= F[i]; y++) {
            visited[D[i]][y] = 1;
        }
    }
    stack<pair<int, int>> S;
    S.emplace(zero_x, zero_y);
    while (!S.empty()) {
        auto [x, y] = S.top(); S.pop();
        if (visited[x][y]) continue;
        visited[x][y] = 1;
        if (x == 0 || x == X.size() * 2 || y == 0 || y == Y.size() * 2) {
            cout << "INF\n";
            return 0;
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + DX[i];
            int ny = y + DY[i];
            if (0 <= nx && nx < X.size() * 2 + 1 && 0 <= ny && ny < Y.size() * 2 + 1) {
                S.emplace(nx, ny);
            }
        }
    }
    Int ans = 0;
    for (int i = 0; i < X.size() - 1; i++) {
        for (int j = 0; j < Y.size() - 1; j++) {
            if (visited[i * 2 + 1][j * 2 + 1]) {
                ans += (X[i + 1] - X[i]) * (Y[j + 1] - Y[j]);
            }
        }
    }
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 479228
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * Built using CHelper plug-in Actual solution is at the top
 */
public class Main {
	public final static double MAX_T = 1000000;
	public final static double MIN_T = 0;
	public static int s = 0;

	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskC solver = new TaskC();
		solver.solve(1, in, out);
		out.close();
	}

	static class TaskC {

		public void solve(int testNumber, InputReader in, PrintWriter out) {
			int n = in.nextInt();
			long i = 1;
			while ((i << 1) <= n) {
				i <<= 1;
			}
			out.println(i);

		}

	}

	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public long nextLong() {
			return Long.parseLong(next());
		}

		public double nextFloat() {
			return Double.parseDouble(next());
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

	}
}


Measured memory_bytes: 23380
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <set>
#include <queue>
#include <stack>
using namespace std;
typedef long long int ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define drep(i, n) for(int i = n - 1; i >= 0; i--)
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl

const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;
const int mod = 1000000007;
#define PI 3.14159265359;

void P(int x) {cout << x << endl;}
void P(long x) {cout << x << endl;}
void P(double x) {cout << x << endl;}
void P(ll x) {cout << x << endl;}
void P(string x) {cout << x << endl;}
void P(char x) {cout << x << endl;}

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main() {
  int n, m;
  cin >> n >> m;
  set<int> one, enu;
  rep (i, m) {
    int a, b;
    cin >> a >> b;
    if (a == 1) one.insert(b);
    else if (b == n) enu.insert(a);
  }

  for (auto itr = one.begin(); itr != one.end(); itr++) {
    auto itr2 = enu.find(*itr);
    if (itr2 != enu.end()) {
      P("POSSIBLE");
      return 0;
    }
  }
  P("IMPOSSIBLE");


  return 0;
}

Measured memory_bytes: 9600
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(p,a,b)    for(int p=a;p<b;p++)
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define INF 0x3f3f3f3f



int main() {
    #ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("o2.txt", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int a,b;
    cin>>a>>b;
    cout<<a*b;
    return 0;
}

Measured memory_bytes: 3648
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;
int main() {
    int N, count=0;
    cin >> N;
    for (int j=0; j < N; ++j) {
        int x;
        cin >> x;
        while (x % 2 == 0) {
            count += 1;
            x /= 2;
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int man = 2e5+10;
#define IOS ios::sync_with_stdio(0)
template <typename T>
inline T read(){T sum=0,fl=1;int ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')fl=-1;
for(;isdigit(ch);ch=getchar())sum=sum*10+ch-'0';
return sum*fl;}
template <typename T>
inline void write(T x) {static int sta[35];int top=0;
do{sta[top++]= x % 10, x /= 10;}while(x);
while (top) putchar(sta[--top] + 48);}
template<typename T>T gcd(T a, T b) {return b==0?a:gcd(b, a%b);}
template<typename T>T exgcd(T a,T b,T &g,T &x,T &y){if(!b){g = a,x = 1,y = 0;}
else {exgcd(b,a%b,g,y,x);y -= x*(a/b);}}
#ifndef ONLINE_JUDGE
#define debug(fmt, ...) {printf("debug ");printf(fmt,##__VA_ARGS__);puts("");}
#else
#define debug(fmt, ...)
#endif
typedef long long ll;
const ll mod = 1e9+7;
int a[5][5];
map<int,int>sp;

int main() {
    #ifndef ONLINE_JUDGE
        //freopen("in.txt", "r", stdin);
        //freopen("out.txt","w",stdout);
    #endif
    for(int i = 1;i <= 3;i++){
        for(int j = 1;j <= 3;j++){
            cin >> a[i][j];
        }
    }
    int m;
    cin >> m ;
    for(int i = 1;i <= m;i++){
        int x;
        cin >> x;
        sp[x] = 1;
    }
    bool f = 0;
    for(int i = 1;i <= 3;i++){
        if(sp.count(a[i][1])&&sp.count(a[i][2])&&sp.count(a[i][3])){
            f = 1;
        }
    }
    for(int i = 1;i <= 3;i++){
        if(sp.count(a[1][i])&&sp.count(a[2][i])&&sp.count(a[3][i])){
            f = 1;
        }
    }
    if(sp.count(a[1][1])&&sp.count(a[2][2])&&sp.count(a[3][3])){
        f = 1;
    }
    if(sp.count(a[1][3])&&sp.count(a[2][2])&&sp.count(a[3][1])){
        f = 1;
    }
    if(f)cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

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

int n,a[200001],jiejin=-1e9,ji;
double shu;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	shu=(double)a[n]/2;
	for(int i=1;i<n;i++)
	{
		if(abs(a[i]-shu)<abs(jiejin-shu))
		{
			ji=i;
			jiejin=a[i];
		}
	}
	printf("%d %d\n",a[n],jiejin);
	return 0;
}

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

const int MAX_N = 1000000;

vector<int> a(MAX_N,0);

int f(int n){
  if(n % 2 == 0) return n / 2;
  else return 3*n + 1;
}

int main(){
  int s,ans;
  cin >> s;
  a[0]=s;

  //init
  for(int i=1;i<=MAX_N;++i){
    a[i] = f(a[i-1]);
  }

  //search
  for(int i=0;i<=MAX_N;++i){
    for(int j=i+1;j<=MAX_N;++j){
      if(a[i] == a[j]) {
        ans = j+1;
        cout << ans << endl;
        return 0;
      }
    }
    }

  return 0;
}


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

#define int long long 

using namespace std;

const int N = 1e5;
const int inf = 1e9 + 10;

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, ww;
  cin >> n >> ww;
  vector<int> w(n), v(n);
  for (int i = 0; i < n; i++) {
    cin >> w[i] >> v[i];
  } 
  vector<int> dp(N + 1, inf);
  dp[0] = 0;
  for (int i = 0; i < n; i++) {
    for (int j = N; j >= 0; j--) {
      if (j + v[i] <= N && dp[j] != inf) {
        dp[j + v[i]] = min(dp[j + v[i]], + w[i] + dp[j]);
      }
    }
  }
  int res = 0;
  for (int i = N; i >= 0; i--) {
    if (dp[i] <= ww) {
      res = i;
      break;
    }
  }
  cout << res << "\n";
  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <cstdio>
#include <cctype>

using namespace std;

int main(void) {

    while (true) {
        string line;
        getline(cin, line);

        if (line.size() == 1 && line[0] == '0') { break; }

        int total = 0;
        for (int i = 0; i < line.size(); ++i) {
            total += line[i] - '0';
        }
        printf("%d\n", total);
    }

    return 0;
}

Measured memory_bytes: 1192
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1000000007LL;
const int INF = LLONG_MAX;

signed main(){
    
    int h, w; cin >> h >> w;
    int n; cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    vector<vector<int> > ans(h, vector<int> (w));
    int idx = 0;
    for(int i = 0; i < h; i++){
        if(i % 2 == 0){

            for(int j = 0; j < w; j++){
                ans[i][j] = idx + 1;
                a[idx]--;
                if(a[idx] == 0) idx++;
            }

        }else{

            for(int j = w - 1; j >= 0; j--){
                ans[i][j] = idx + 1;
                a[idx]--;
                if(a[idx] == 0) idx++;
            }
        }
    }

    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: 512
n=int(input())
l=list(map(int,input().split()))
ml=max(l)
m=[0]*(ml+1)
for i in l:
    m[i]+=1
for i in range(ml+1):
    if m[i]>=1:
        for j in range(2*i,ml+1,i):
            if m[j]>0:
                m[j]=0
                #print(j)
for i in range(ml+1):
    if m[i]>=2:
        m[i]=0
print(sum(m))

Measured memory_bytes: 117136
#include <iostream>

using namespace std;

const int kM = 1000000007;
int n;
long long s, a, ans;
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a;
    ans = (ans + s * a) % kM;
    s = (s + a) % kM;
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 3628
n = int(input())

t = 0
i = 1

while t < n:

    t += i
    i += 1

pass_num = t - n

s = 0
i = 1
while s < n:
    if i != pass_num:
        s += i
        print(i)
        i += 1
    else:
        i += 1

Measured memory_bytes: 42456
s = input().split()
a,b = int(s[0]),int(s[1])
while not(a == 0 and b == 0):
    if(a<b):
        print(a,b)
    else:
        print(b,a)
    s = input().split()
    a,b = int(s[0]),int(s[1])


Measured memory_bytes: 5616
n,q=map(int,input().split())
from collections import deque
edge=[[] for _ in range(n)]
ans=[0]*n
for i in range(n-1):
  a,b=map(lambda x:int(x)-1,input().split())
  edge[a].append(b)
  edge[b].append(a)

for i in range(q):
  p,x=map(int,input().split())
  p-=1
  ans[p]+=x

done=[False]*n
q=deque([])
q.append(0)
done[0]=True
while q:
  v=q.popleft()
  done[v]=True
  for c in edge[v]:
    if done[c]==False:
      ans[c]+=ans[v]
      q.append(c)
    
print(*ans) 
  


Measured memory_bytes: 127620
#include<bits/stdc++.h>
using namespace std;
typedef pair< int , int > Pi;

int main(){
  int n, m, h, k, s[1000];
  Pi ab[100000], c[100000], d[100000];
  int ans[1000], pos[1000];

  while(scanf("%d %d %d %d", &n, &m, &h, &k), n){
    for(int i = 0; i < n; i++){
      scanf("%d", &s[i]);
      ans[i] = i;
    }
    for(int i = 0; i < m; i++){
      scanf("%d %d", &ab[i].second, &ab[i].first);
    }
    sort( ab, ab + m);
  
    int base = 0;
    for(int i = 0; i < m; i++){
      swap(ans[ab[i].second - 1], ans[ab[i].second]);
      d[i] = Pi( ans[ab[i].second - 1], ans[ab[i].second]);
    }
    for(int i = 0; i < n; i++){
      if(ans[i] < k) base += s[i];
      pos[ans[i]] = i;
    }

    int ret = base;

    for(int i = 0; i < m; i++){
      long long res = base;
      
      if(d[i].first < k){
        res -= s[pos[d[i].first]];
        res += s[pos[d[i].second]];
      }
      if(d[i].second < k){
      res += s[pos[d[i].first]];
      res -= s[pos[d[i].second]];
      }
      ret = min<int>( res, ret);
    }
    
    cout << ret << endl;
  }  
}
  

Measured memory_bytes: 3564
#include <iostream>
using namespace std;
#define MAX 502
#define MAX_P 10002

int main(){
    int n,m;
    
    while(cin >> n >> m ,n+m){
        int a,b,tmp[MAX]={0},cnt=0,friA[MAX_P]={0},friB[MAX_P]={0},t=0;
        for(int i = 0 ; i < m ; i++){
            cin >> a >> b;
            if(a == 1){
                tmp[b] = 1;
            }
            else{
                friA[t] = a;
                friB[t] = b;
                t++;
                }
        }
        
        for(int i = 0 ; i < t ; i++){
            if(tmp[friA[i]]==1&&!tmp[friB[i]]) tmp[friB[i]] = 2;
            else if(!tmp[friA[i]]&&tmp[friB[i]]==1) tmp[friA[i]] = 2;
        }
        
        for(int i = 0 ; i < MAX ; i++){
            if(tmp[i] > 0){
                cnt++;
            }
        }
        cout << cnt << endl;
    }
    
    return 0;
}

Measured memory_bytes: 1248
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

int n;
ll a[6000];
vector<int>E[6000];
int siz[6000];
ll dp[6000][6000];
bool dp2[6000][6000];

void dfs(int v,int p){
	for(int u:E[v]){
		if(u==p)continue;
		dfs(u,v);
	}
	vector<ll>prv1(n*2),nex1(n*2);
	vector<bool>prv2(n*2),nex2(n*2);
	rep(i,n)prv1[i]=INFL;
	prv1[0]=a[v];
	if(a[v]>0)prv2[0]=true;
	siz[v]=1;
	for(int u:E[v]){
		if(u==p)continue;
		for(int i=siz[v]+siz[u];i>=0;i--){
			nex1[i]=INFL;
			nex2[i]=false;
		}
		rep(i,siz[v]+1){
			rep(j,siz[u]+1){
				if(dp[u][j]<0||dp2[u][j]){
					nex1[i+j+1]=min(nex1[i+j+1],prv1[i]);
					nex2[i+j+1]=(nex2[i+j+1]|prv2[i]);
				}
				nex1[i+j]=min(nex1[i+j],prv1[i]+dp[u][j]);
				nex2[i+j]=(nex2[i+j]|(prv2[i]&dp2[u][j]));
			}
		}
		siz[v]+=siz[u];
		swap(prv1,nex1);
		swap(prv2,nex2);
	}
	rep(i,n){
		dp[v][i]=prv1[i];
		dp2[v][i]=prv2[i];
	}
}
int main(){
	scanf("%d",&n);
	rep(i,n)scanf("%lld",&a[i]);
	rep(i,n-1){
		int a,b;scanf("%d%d",&a,&b);a--;b--;
		E[a].push_back(b);
		E[b].push_back(a);
	}
	dfs(0,-1);
	rep(i,n){
		if(dp[0][i]<0||dp2[0][i]==true){
			cout<<i<<endl;
			return 0;
		}
	}
}

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

int main(void){
    int n,k;
    cin >> n >> k;
    ll a[n],b[n];
    rep(i,n){
        cin >> a[i];
        b[i] = a[i];
    }
    
    ll ans = 1e18;
    if(n == 1)ans = abs(a[0]);
    for(int i = k-1;i < n;i++){
        ans = min(ans,abs(a[i]-a[i-k+1])+min(abs(a[i]),abs(a[i-k+1])));
    }
    cout << ans << endl;
}


Measured memory_bytes: 5196
#include <bits/stdc++.h>
using namespace std;
int main()
{
    using ll = long long;
    ll n, m;
    cin >> n >> m;
    using P = pair<ll, ll>;
    vector<P> d(n);
    for(ll i = 0; i < n; i++)
    {
        ll a, b;
        cin >> a >> b;
        d[i] = P(a, b);
    }
    sort(d.begin(), d.end());

    ll ans = 0;
    for(ll i = 0; i < n; i++)
    {
        if(m == 0) break;
        P p = d[i];
        ll a = p.first;
        ll b = p.second;
        ans += a * min(m, b);
        m -= min(m, b);
    }
    cout << ans << endl;
}




Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define all(c) c.begin(), c.end()
#define gmax(x,y) x=max(x,y)
#define gmin(x,y) x=min(x,y)
using namespace std;

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

int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	int h,n;
	cin >> h >> n;
	int sum = 0;
	rep(i,0,n){
		int x;
		cin >> x;
		sum += x;
	}
	cout << (sum >= h ? "Yes" : "No") << '\n';
}


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

bool counter(int N){
  vector<int> s(5);
  for(int i = 0; i < 5; i++){
    s.at(i) = N % 10;
    N /= 10;
  }
  
  int count = 0;
  if(s.at(0) == s.at(4) && s.at(1) == s.at(3)){
   return true;
  }
  else{
    return false;
  }
}
  
    



int main(){
  int A, B;
  cin >> A >> B;
  
  int N = A;
  int count = 0;
  while(N <= B){
    if(counter(N)){
      count++;
    }
    N++;
  }
  
  cout << count << endl;
}
      
      

Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def main():
    N = int(readline())
    A = [0] + [int(i) for i in readline().split()]
    table = [0 for _ in range(N+1)]
    for i in range(N, 0, -1):
        table[i] = (sum(table[::i])%2)^A[i]

    print(sum(table))
    for i in range(N):
        if table[i+1]:
            print(i+1, end=' ')
if __name__ == '__main__':
    main()

Measured memory_bytes: 8360
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int[] d = new int[n];
        for(int i=0; i<n; i++) {
            d[i] = in.nextInt();
        }

        int max = 0;
        for(int dropCount=0; dropCount<n; dropCount++) {
            for(int fromLeftCount=0; fromLeftCount<=k-dropCount; fromLeftCount++) {
                int fromRightCount = Math.max(k-dropCount-fromLeftCount, 0);
                ArrayList<Integer> gems = new ArrayList<>();
                for(int i=0; i<fromLeftCount&&i<n; i++) {
                    gems.add(d[i]);
                }
                for(int i=n-1; i>=n-fromRightCount&&i>=fromLeftCount; i--) {
                    gems.add(d[i]);
                }
                Collections.sort(gems);
                for(int i=0; i<dropCount&&i<gems.size(); i++) {
                    if(gems.get(i)<0) {
                        gems.set(i, 0);
                    }
                }
                int sum = 0;
                Iterator<Integer> it = gems.iterator();
                while(it.hasNext()) {
                    sum += it.next();
                }
                max = Math.max(max, sum);
            }
        }
        System.out.println(max);
    }
}


Measured memory_bytes: 33300
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>
#include <functional>
#include <iomanip>

using namespace std;

#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ;
#endif

#define EPS (1e-10)
#define equals(a,b) (fabs((a)-(b)) < EPS)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;

const int MAX_ROW = 63;
const int MAX_COL = 1e5+10;

struct BitMatrix {
    int H, W;
    bitset<MAX_COL> val[MAX_ROW];
    BitMatrix(int m = 1, int n = 1) : H(m), W(n) {}
    inline bitset<MAX_COL>& operator [] (int i) {return val[i];}
};

void GaussJordan(BitMatrix &A, bool is_extended = false) {
    vector<bool> used(A.H,0);

    for (int col = 0; col < A.W; ++col) {
        if (is_extended && col == A.W - 1) break;
        int pivot = -1;
        for (int row = 0; row < A.H; ++row) {
            if(used[row]) continue;
            if (A[row][col]) {
                pivot = row;
                break;
            }
        }
        if (pivot == -1) continue;
        for (int row = 0; row < A.H; ++row) {
            if (row != pivot && A[row][col]) A[row] ^= A[pivot];
        }
        used[pivot] = true;
    }
}


signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N; cin >> N;
    VL A(N);
    REP(i,N) cin >> A[i];
    const int MD = 60;

    LL res = 0;
    BitMatrix B(MD+1,N+1);
    vector<bool> cannot(MD+1,0);
    for(LL d = MD; d >= 0; d--){
        int num = 0;
        REP(i,N) if(A[i]&(1LL << d)) num++;

        if(num == 0){
            cannot[d] = 1;
            continue;
        }else if(num&1){
            cannot[d] = 1;
            res += (1LL << d);
            continue;
        }

        REP(i,N){
            if(A[i]&(1LL<<d)) B[MD-d][i] = 1;
        }
        B[MD-d][N] = 1;

    }

    GaussJordan(B,true);
    for(int d = MD; d >= 0; d--){
        if(cannot[d]) continue;

        bool ok = false;
        REP(i,N) if(B[MD-d][i]) ok = true;
        if(!B[MD-d][N]) ok = true;

        if(ok) res += (2LL << d);
    }
    cout << res << endl;

}


Measured memory_bytes: 1920
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())



n,m=map(int,input().split())
A=[0]*m
B=[0]*m
for i in range(m-1,-1,-1):
  A[i],B[i]=map(int,input().split())
  A[i]=A[i]-1
  B[i]=B[i]-1
D=[n*(n-1)//2]
C=UnionFind(n)
for i in range(m-1):
  if D[-1]==0:
    D.append(0)
  elif C.find(A[i])!=C.find(B[i]):
    D.append(D[-1]-C.size(A[i])*C.size(B[i]))
    C.union(A[i],B[i])
  else:
    D.append(D[-1])
for i in range(m-1,-1,-1):
  print(D[i])

Measured memory_bytes: 17004
#include <iostream>
 
using namespace std;
 
long long int max(long long int a, long long int b)
{
    return (a > b) ? a : b;
}
 
long long int knapSack(long long int W, long long int wt[], long long int val[], long long int n)
{
    int i, w;
    long long int K[n + 1][W + 1];
 
    // Build table K[][] in bottom up manner
    for (i = 0; i <= n; i++)
    {
        for (w = 0; w <= W; w++)
        {
            if (i == 0 || w == 0)
                K[i][w] = 0;
            else if (wt[i - 1] <= w)
                K[i][w]
                        = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
            else
                K[i][w] = K[i - 1][w];
        }
    }
 
    return K[n][W];
}
 
int main()
{
    long long int n, W;
    cin >> n;cin >> W;
    long long int val[n], wt[n];
    for (long long int i = 0; i < n; i++)
    {cin >> wt[i];
        cin >> val[i];
        
    }
 
    cout << knapSack(W, wt, val, n);
 
    return 0;
}

Measured memory_bytes: 79104
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int H = sc.nextInt();
        int W = sc.nextInt();
        int N = sc.nextInt();
        int Sr = sc.nextInt();
        int Sc = sc.nextInt();
        String S = sc.next();
        String T = sc.next();


        //Row
        int left=0;
        int right=W -1;

        for (int i = N-1; i >=0; i--) {
            char s = S.charAt(i);
            char t = T.charAt(i);
            if(t=='R') left = Math.max(left-1,0);
            if(t=='L') right = Math.min(right+1,W-1);
            if(s=='L') left++;
            if(s=='R') right--;

            if(left>right){
                System.out.println("NO");
                return;
            }
        }

        int top=0;
        int bottom=H -1;
        for (int i = N-1; i >= 0 ; i--) {
            char s = S.charAt(i);
            char t = T.charAt(i);
            if(t=='D') top = Math.max(top-1,0);
            if(t=='U') bottom = Math.min(bottom+1,H-1);
            if(s=='U') top++;
            if(s=='D') bottom--;

            if(top>bottom){
                System.out.println("NO");
                return;
            }

        }

        if( left<=Sc-1 && Sc-1 <= right && top<= Sr-1 && Sr-1 <= bottom){
            System.out.println("YES");
        }else{
            System.out.println("NO");
        }
    }
}

Measured memory_bytes: 28184
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#define cmin(a,b) (a>(b)?a=(b),1:0)
#define cmax(a,b) (a<(b)?a=(b),1:0)
#define dmin(a,b) ((a)<(b)?(a):(b))
#define dmax(a,b) ((a)>(b)?(a):(b))
namespace io
{
	int F()
	{
		int n=0,F=1;
		char ch;
		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		ch=='-'?F=0:n=ch-'0';
		while((ch=getchar())>='0'&&ch<='9')n=n*10+ch-'0';
		return F?n:-n;
	}
}
const int M=1000000007;
int li[22];
int fr[22];
int f[133333];
int r0[133333];
int pc[266666];
int b3[133333];
int v[133333],pv;
int g[44444444];
int h[133333];
int ex2[333];
int lg[133333];
int fu[133333];
int main()
{
	int n=io::F(),m=io::F();
	for(register int i=1;i<=m;++i)
	{
		int x=n-io::F(),y=n-io::F();
		li[x]|=1<<y;
		fr[y]|=1<<x;
	}
	for(register int i=2;i<1<<n;++i)lg[i]=lg[i>>1]+1;
	ex2[0]=1l;
	for(register int i=1;i<=300;++i)ex2[i]=(ex2[i-1]<<1)%M;
	for(register int i=0;i<1<<n-1;++i)
		if(!(i&1))r0[i]=1;
			else r0[i]=r0[i>>1]<<1;
	for(register int i=1;i<1<<n;++i)pc[i]=pc[i^i&-i]+1;
	for(register int i=1;i<1<<n-1;++i)b3[i]=i&1?b3[i-1]+1:b3[i>>1]*3;
	for(register int i=1;i<1<<n-1;++i)fu[i]=i&1<<n-2?i|1<<n-1:i;
	#define G(x,y) g[b3[x]+b3[y]*2]
	for(register int i=1;i<1<<n-1;++i)
	{
		G(0,i)=1;
		pv=0;
		for(register int j=(1<<n-1)-1&~i;j;j=(j-1)&~i)if((j&-j)>(i&-i))v[++pv]=j;
		for(register int *j=v+pv;j!=v;--j)
		{
			int now=lg[*j&-*j];
			G(*j,i)=G(*j^*j&-*j,i)*(long long)(ex2[pc[li[now]&i]]-1)%M;
			if(now==n-2)G(*j,i)=G(*j,i)*(long long)(ex2[pc[li[n-1]&i]]-1)%M;
		}
	}
	f[0]=1;
	for(register int i=0;i<1<<n-1;++i)
		if(f[i])
		{
			pv=0;
			for(register int j=(1<<n-1)-1&~i;j;j=(j-1)&~i)if(j&r0[i])v[++pv]=j;
			for(register int* j=v+pv;j!=v;--j)
			{
				int now=*j^r0[i];
				now=now&-now;
				if(*j==r0[i])h[*j]=pc[fr[lg[r0[i]]]&fu[i]];
					else h[*j]=h[*j^now]+pc[fr[lg[now]]&fu[i]];
				int tmp=(long long)ex2[h[*j]]*G((1<<n-1)-1^i^*j,*j)%M;
				f[i|*j]=(f[i|*j]+(long long)f[i]*tmp)%M;
			}
		}
	printf("%d\n",(ex2[m]+M-f[(1<<n-1)-1])%M);
	return 0;
}

Measured memory_bytes: 23424