akhauriyash/Code-Regression huggingface dataset:
import java.io.{BufferedReader, IOException, InputStream, InputStreamReader}
import java.util.StringTokenizer

import scala.collection.mutable
import scala.util.Sorting
import math.{abs, max, min}
import scala.collection.mutable.ArrayBuffer

object Main {
  def solve(): Unit = {
    val sc = new InputReader(System.in)
    val N = sc.nextInt()
    val K = sc.nextInt()
    val L = sc.nextInt()

    var i = 0
    val uf_road = new UnionFind(N + 1)
    i = 0
    while (i < K) {
//    (0 until K) foreach { _ =>
      uf_road.unite(sc.nextInt(), sc.nextInt())
      i += 1
    }

    val uf_rail = new UnionFind(N + 1)
    i = 0
    while (i < L) {
//    (0 until L) foreach { _ =>
      uf_rail.unite(sc.nextInt(), sc.nextInt())
      i += 1
    }

    val group = new java.util.HashMap[(Int, Int), Int](N) // key => group
    i = 1
    while (i <= N) {
//    (1 to N) foreach { i =>
      val k = (uf_road.find(i), uf_rail.find(i))
      group.put(k, i)
      i += 1
    }
    val i2g = Array.ofDim[Int](N + 1) // i => group
    i = 1
    while (i <= N) {
//    (1 to N) foreach { i =>
      val k = (uf_road.find(i), uf_rail.find(i))
      i2g(i) = group.get(k)
      i += 1
    }
    val count = Array.ofDim[Int](N + 1) // group => count
    i = 1
    while (i <= N) {
//    (1 to N) foreach { i =>
      count(i2g(i)) += 1
      i += 1
    }
    i = 1
    while (i <= N) {
//    (1 to N) foreach { i =>
      if (i > 1) print(" ")
      print(count(i2g(i)))
      i += 1
    }

//    val count = mutable.Map[(Int, Int), Int]()
//    var i = 1
//    while(i <= N) {
//      val k = key(i)
//      if (!(count contains k)) count(k) = 0
//      count(k) = count(k) + 1
//      i += 1
//    }
//
//    i = 1
//    while(i <= N) {
//      if (i > 1) print(" ")
//      print(count(key(i)))
//      i += 1
//    }
//    println()
//    val count = ((1 to N) map key).groupBy(identity).mapValues(_.size)
//    val ans = ((1 to N) map (key _).andThen (count(_))).mkString(" ")
//    println(ans)
  }

  def main(args: Array[String]): Unit = {
    solve()
  }



  class InputReader(val stream: InputStream) {
    val reader = new BufferedReader(new InputStreamReader(stream), 32768)
    var tokenizer: StringTokenizer = null

    def next: String = {
      while (tokenizer == null || !tokenizer.hasMoreTokens)
        tokenizer = new StringTokenizer(reader.readLine)
      tokenizer.nextToken
    }

    def nextInt(): Int = next.toInt
    def nextLong(): Long = next.toLong
    def nextChar(): Char = next.charAt(0)
  }

  class UnionFind(n: Int) {
    private val par = Array.ofDim[Int](n)
    (0 until n) foreach (i => par(i) = i)
    private val rank = Array.ofDim[Int](n)

    def find(x: Int): Int = {
      if (par(x) == x) x
      else {
        par(x) = find(par(x))
        par(x)
      }
    }

    def unite(x: Int, y: Int): Unit = {
      val x1 = find(x)
      val y1 = find(y)
      if (x1 != y1) {
        if (rank(x1) < rank(y)) {
          par(x1) = y1
        } else {
          par(y1) = x1
          if (rank(x1) == rank(y1)) rank(x1) += 1
        }
      }
    }
  }
}


Measured memory_bytes: 98476
import java.util.*;

public class Main{
	public static void main(String arg[]){
		Scanner sc = new Scanner(System.in);
		long h=sc.nextLong();
		long cnt=1;
		while(h > 1){
			h=h/2;
			cnt*=2;
		}
		System.out.println(2*cnt-1);
	}
}

Measured memory_bytes: 21716
import sys
input = sys.stdin.readline


def make_divisors(n):
    divisors = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)

    # divisors.sort()
    return divisors


n = int(input())
cnt = 0

for i in range(1, n + 1):
    if i % 2 == 1:
        if len(make_divisors(i)) == 8:
            cnt += 1

print(cnt)


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

void printv(vector<string> a, int n) {
    rep(i, n) {
        printf("%s", a[i].c_str());
        if (i != n-1) printf(" ");
    }
    printf("\n");
}

void bubble_sort(vector<string> &a, int n) {
    bool flag = false;
    while (!flag) {
        flag = true;
        rep(i, n-1) {
            if (a[i][1]-'0' > a[i+1][1]-'0') {
                swap(a[i], a[i+1]);
                flag = false;
            }
        }
    }
}

void select_sort(vector<string> &a, int n) {
    for (int i = 0; i < n; i++) {
        int min_j = i;
        for (int j = i; j < n; j++) {
            if (a[j][1]-'0' < a[min_j][1]-'0') min_j = j;
        }
        if (i != min_j) {
            swap(a[i], a[min_j]);
        }
    }
}

int main() {
    int n;
    scanf("%d", &n);
    vector<string> card(n);
    rep(i, n) {
        cin >> card[i];
    }

    vector<string> bubble = card;
    vector<string> select = card;

    bubble_sort(bubble, n);
    printv(bubble, n);
    printf("Stable\n");

    select_sort(select, n);
    printv(select, n);

    bool same = true;
    rep(i, n) {
        if (bubble[i] != select[i]) {
            same = false;
            break;
        }
    }
    if (same) printf("Stable\n");
    else printf("Not stable\n");
}


Measured memory_bytes: 3328
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <unordered_map>
#define rep(i,n) for (int i=0; i<n;++i)
#define rep_down(i,n) for (int i=n-1; i>=0;--i)
#define ALL(a)  (a).begin(),(a).end()
typedef long long ll;
using namespace std;
const ll MOD = 1000000007LL;
const int INF = 1000000007;
ll N;

int dfs(ll s){
  if (s > N) return 0;
  bool flag_3 = false;
  bool flag_5 = false;
  bool flag_7 = false;
  ll z = s;
  while(z>0){
    int a = z%10;
    if (a==3) flag_3 = true;
    if (a==5) flag_5 = true;
    if (a==7) flag_7 = true;
    if (flag_3&&flag_5&&flag_7) break;
    z/=10;
  }
  int ret = flag_3&&flag_5&&flag_7?1:0;
  ret += dfs(s*10+3);
  ret += dfs(s*10+5);
  ret += dfs(s*10+7);
  return ret;
}

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

  cin >> N;
  cout << dfs(0ll) << "\n";
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

class Main {

	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		int N = sc.nextInt(),i, h[] = new int[N];
		for(i=0;i<N;i++)h[i]=sc.nextInt();
		int dp[]=new int[N+1];
		dp[0]=0;
		dp[1]=Math.abs(h[1]-h[0]);
		for(i=2;i<N;i++) {
			dp[i]=Math.min(dp[i-1]+Math.abs(h[i]-h[i-1]), dp[i-2]+Math.abs(h[i]-h[i-2]));
		}
		System.out.println(dp[N-1]);
	}
}

Measured memory_bytes: 59428
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  ll n;
  cin >> n;
  vl a(n);
  rep(i, n) cin >> a[i];
  vector<vl> dp(n + 5, vl(3, -1e18));
  int k = n % 2 + 1;
  dp[0][k] = 0;
  rep(i, n) rep(j, 3) {
    if(dp[i][j] == -1e18) continue;
    if(j == 2) dp[i + 2][0] = max(dp[i + 2][0], dp[i][j]);
    if(j >= 1) dp[i + 1][j - 1] = max(dp[i + 1][j - 1], dp[i][j]);
    dp[i + 2][j] = max(dp[i + 2][j], dp[i][j] + a[i]);
  }
  ll ans = -1e18;
  rep2(i, n, n + 2) rep(j, 2) ans = max(ans, dp[i][j]);
  cout << ans << endl;
}


Measured memory_bytes: 15592
use std::io::Read;
use std::cmp;

fn main() {
    let mut buf = String::new();

    // 標準入力から全部bufに読み込む
    std::io::stdin().read_to_string(&mut buf);

    // 読み込んだStringを空白で分解する
    let mut iter = buf.split_whitespace();

    // aの読み込み
    let a: i32 = iter.next().unwrap().parse().unwrap();
    // bの読み込み
    let b: i32 = iter.next().unwrap().parse().unwrap();
    // cの読み込み
    let c: i32 = iter.next().unwrap().parse().unwrap();

    // 容器2に残る水の量
    let x: i32 = c - (a - b);

    if x <= 0 {
        println!("{}", 0);
    } else {
        println!("{}", x);
    }
}

Measured memory_bytes: 4352
//{{{
#include<algorithm>
#include<cmath>
#include<deque>
#include<fstream>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<random>
#include<set>
#include<sstream>
#include<sys/time.h>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(printde) FUNC(printdbe) FUNC(printdwe) FUNC(printdu);
#endif
template <template <class T, class = std::allocator<T>> class V, class E>
istream& operator >> (istream& in, V<E>& v){ for(auto& e : v){ in >> e; } return in; }
//}}}

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    int n; cin >> n;
    cout << n * n * n << '\n';
}


Measured memory_bytes: 888
N = int(input())
T = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    T[a].append(b)
    T[b].append(a)


colors = [-1] * N
stack = [(0, 0)]
while stack:
    n, color = stack.pop()
    colors[n] = color
    for to in T[n]:
        if colors[to] != -1:
            continue
        stack.append((to, color ^ 1))


# あまり１、あまり２、あまり０になるように並び替え
X = [[] for _ in range(3)]
for n in range(1, N + 1):
    X[n % 3].append(n)
X.append(X[0])
del X[0]


ans = []
x12, x3 = X[0] + X[1], X[2]
if colors.count(0) <= N // 3:
    for color in colors:
        if color == 0:
            ans.append(x3.pop())
        elif x12:
            ans.append(x12.pop())
        else:
            ans.append(x3.pop())

elif colors.count(1) <= N // 3:
    for color in colors:
        if color == 1:
            ans.append(x3.pop())
        elif x12:
            ans.append(x12.pop())
        else:
            ans.append(x3.pop())

else:
    for color in colors:
        if X[color]:
            ans.append(X[color].pop())
        else:
            ans.append(X[2].pop())

print(' '.join(map(str, ans)))


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

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x,n) bitset<n>(x)
#define PI 3.14159265358979323846

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

//-----------------------------------------------------------------------------

int n,a[110],ma,mi=INF,cnt[110];

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

	cin>>n;
	REP(i,n) {
		cin>>a[i];
		ma=max(ma,a[i]);
		cnt[a[i]]++;
	}
	FOR(i,1,(ma+1)/2) {
		if(cnt[i]!=0) {
			cout<<"Impossible"<<endl;
			return 0;
		}
	}
	if(cnt[(ma+1)/2]!=(ma&1?2:1)) {
		cout<<"Impossible"<<endl;
		return 0;
	}
	FOR(i,(ma+1)/2+1,ma+1) {
		if(cnt[i]<2) {
			cout<<"Impossible"<<endl;
			return 0;
		}
	}
	cout<<"Possible"<<endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <string.h>
using namespace std;

int main()
{
  char s;
  cin>>s;
  string ans="consonant";
  if(s=='a'||s=='i'||s=='u'||s=='e'||s=='o') ans="vowel";
  cout<< ans <<endl;
}


Measured memory_bytes: 256
#include<stdio.h>
int main() {
	int x, y,d,i=0;
	while (1) {
		i++;
		if (i == 3001) break;
		scanf("%d %d", &x, &y);
		if (x == 0 && y == 0) break;
		if (x > y) {
			d = x;
			x = y;
			y = d;
		}
		printf("%d %d\n", x, y);
	}
	return 0;
}

Measured memory_bytes: 2556
#include <iostream>
using namespace std;
int main(void){
    cin.tie(0);
   	ios::sync_with_stdio(false);
    
    int n;
    int s[100000];
    int t[100000];
    cin >> n;
    
    for(int i=0; i<n; i++){
        cin >> s[i];
        t[s[i]-1] = i+1;
    }
    
    for(int j=0; j<n; j++){
        cout << t[j] << " " ;
    }
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define fi first
#define se second
#define mp make_pair
#define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++)
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
typedef long long llong;
char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define print(a) cout << a << endl;
#define MOD llong(1e9+7)
#define MAX int(2 * 1e5 +5)
#define debug(x)  cout << #x << " = " << (x) << endl;
#define pi acos(-1.0)
#define int llong
#define INF llong(1e17)
void myprint(int* A,int A_num){
   REP(i,A_num) cout << A[i] << " ";
   cout << endl;
}

signed main(){
    int n,m;
    cin >> n >> m;
    int s[n];
    int t[m];
    REP(i,n) cin >> s[i];
    REP(i,m) cin >> t[i];

    int dp[n+1][m+1];
    int only[n+1][m+1];

    REP(i,n+1){
        dp[i][0] = 0;
        only[i][0] = 0;
    }
    REP(i,m+1){
        dp[0][i] = 0;
        only[0][i] = 0;
    }
    FOR(i,1,n+1){
        FOR(j,1,m+1){
            if(s[i-1] ==t[j-1] ){
                dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + 1 + only[i][j-1];
                only[i][j] = dp[i-1][j-1] + 1 + only[i][j-1];
            }
            else{
                dp[i][j] = dp[i-1][j] + only[i][j-1];
                only[i][j] = only[i][j-1];
            }
            dp[i][j] %= MOD;
            only[i][j] %= MOD;
        }
    }
    cout << (1 + dp[n][m]) % MOD << endl;

}

Measured memory_bytes: 62848
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define pi M_PI
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int main() {
    string s;
    while (cin >> s && s != "0"){
        int ans = 0;
        REP(i,s.length()){
            ans += s[i] - '0';
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 3140
// template.cpp

// Defines.
//#define DEBUG
#define NUMBER_OF_DIGITS 6

// Includes.
#include <bits/stdc++.h>

#ifdef DEBUG
#include <chrono>
#endif

// Usings.
using namespace std;

// Main function.
int main()
{
#ifdef DEBUG
	chrono::system_clock::time_point start, end;
	
	start = chrono::system_clock::now();
#endif
	
	// settings.
	ios::sync_with_stdio(false);
	
	//cout << fixed;
	//cout << setprecision(NUMBER_OF_DIGITS);
	
	// logic.
	int n;
	cin >> n;
	
	bool can = false;
	for (int i = 1; i <= 9; i++)
	{
		for (int j = 1; j <= 9; j++)
		{
			if (n == (i * j))
			{
				can = true;
				goto END;
			}
		}
	}
	
END:
	if (can == true)
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}

#ifdef DEBUG
	end = chrono::system_clock::now();
	
	double elapsed = chrono::duration_cast<std::chrono::milliseconds>(end-start).count();
	cout << elapsed << "[ms]" << endl;
#endif
	
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector>
#include <string>
#include <stdio.h>
#include <math.h>
#include <cstdlib>
#include <iostream>
#include <cstdlib>
using namespace std;

int main(){
	long long int m,c;
	cin>>m;
	c=(m/500)*1000;
	m=m-(m/500)*500;
	c=c+(m/5)*5;
	cout<<c;
	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

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

/*----------macros----------*/

//output================
#define endl '\n'
#define fcout cout << fixed << setprecision(15)

//typedef===============
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;

//const number==========
constexpr ll INF9   = (ll)1e9 + 1;
constexpr ll INF18  = (ll)1e18 + 1;
constexpr ll MOD    = 1000000007;
constexpr ld PI     = 3.141592653589793L;

//member================
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second

//others================
#define all(x)          (x).begin(), (x).end()
#define rall(x)         (x).rbegin(), (x).rend()
#define rep(i, n)       for(int i = 0; (i) < (int)(n); (i)++)
#define rrep(i, n)      for(int i = n - 1; (i) >= 0 ; (i)--)
#define For(i, a, b)    for(int i = (a); (i) < (int)(b) ; (i)++)
#define CtoI(c)         int((c)) - int('0')

//functions=============
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); }

//vector<int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
//vector<int> dx2 = { 1,1,0,-1,-1,-1,0,1 }, dy2 = { 0,1,1,1,0,-1,-1,-1 };



/*--------additional--------*/



/*----------main------------*/

int main() {
/*----------fastio----------*/
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
/*----------solve-----------*/

    ll n, k; cin >> n >> k;
    vector<int> h(n);
    rep(i, n) cin >> h[i];

    sort(rall(h));
    ll ans = 0;
    for(ll i = k; i < n; i++){
        ans += h[i];
    }

    cout << ans << endl;

return 0;
}

Measured memory_bytes: 3936
h, w = map(int, input().split())
A = [list(map(int, input().split())) for _  in range(h)]
tates = []
moves = []
for j, line in enumerate(A):
    odd = 0
    for i, a in enumerate(line[:w-1]):
        if a%2==1:
            odd ^= 1
        if odd:
            moves.append((j+1, i+1, j+1, i+2))
    tates.append(odd^(line[-1]%2))

odd = 0
for i, a in enumerate(tates[:h-1]):
    if a:
        odd ^= 1
    if odd:
        moves.append((i+1, w, i+2, w))

print(len(moves))
for m in moves:
    print(*m)



Measured memory_bytes: 92164
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using v = vector<ll>;
void dpA(){
    int n;
    cin >> n;
    auto h = vector<ll>(n,0);
    for(ll i =0;i<n;i++) cin >> h[i];

    auto dp = vector<ll>(n+2,1e9);
    
    dp[0] = 0;
    dp[1] = 0;
    for(ll i=1;i<n;i++){
        if(i>=2) dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2])); 
        else if(i>=1) dp[i] = dp[i-1] + abs(h[i]-h[i-1]);
    }
    cout << dp[n-1];
}

void dpB(){
    ll n,k;
    cin >> n >> k;
    auto h = vector<ll>(n+1,0);
    for(ll i=0;i<n;i++) cin >> h[i];

    auto dp = vector<ll>(100000,1e9);
    dp[0] = 0;
    for(ll i=0;i<n;i++){
        for(ll j=1;j<=k;j++){
           if(i+j<=n) dp[i+j] = min(dp[i+j],dp[i] + abs(h[i+j]-h[i]));
        }
    }
    cout << dp[n-1];
}

void dpC(){
    ll n; cin >> n;
    vector<v> a(n,v(3,0));
    for(ll i=0;i<n;i++) cin >> a[i][0] >> a[i][1] >> a[i][2];

    auto dp = vector<v>(n+1,v(3,0));

    for(ll i=0;i<n;i++)
        for(ll today=0;today<3;today++)
            for(ll oday=0;oday<3;oday++)
                if(today!=oday) 
                    dp[i+1][today] = max(dp[i+1][today],dp[i][oday] + a[i][today]);
    
    cout << max(dp[n][0],max(dp[n][1],dp[n][2]));
   
    
}

void dpD(){
    ll N,W;
  	cin >> N >> W;
    auto ww = v(N,0);
    auto vv = v(N,0);
    for(ll i=0;i<N;i++) cin >> ww[i] >> vv[i];

    auto dp = vector<v>(N+1,v(W+1,0));
    
    for (ll i = 0; i < N; i++)
    {
        for (ll j = 0; j <= W; j++)
        {

            if(j-ww[i]>=0) dp[i+1][j] = max(dp[i][j],dp[i][j-ww[i]]+vv[i]);
            else dp[i+1][j] = dp[i][j];
        }    
    }
    cout << dp[N][W];
}

void dpE(){
    ll N,W;
  	cin >> N >> W;
    auto ww = v(N,0);
    auto vv = v(N,0);
    for(ll i=0;i<N;i++) cin >> ww[i] >> vv[i];

    auto dp = vector<v>(N+1,v(1e5+100,1LL<<60));
    dp[0][0] = 0;
  
    for (ll i = 0; i < N; i++)
    {
        for (ll j = 0; j <=1e5+100; j++)
        {
            if(j-vv[i]>=0) dp[i+1][j] = min(dp[i+1][j],dp[i][j-vv[i]]+ww[i]);  
            dp[i+1][j] = min(dp[i+1][j],dp[i][j]);
        }    
    }
  
    ll ans = 0;
    for(auto i=0;i<1e5+100;i++){
        if(dp[N][i] <=W){
            ans = i;
        }
    }
    cout << ans;
}

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

Measured memory_bytes: 80256
let n=read_int()open Array
let a=init n(fun _->Scanf.scanf"%d "(fun e->e))and b=make n 0and c=make 10001 0;;iter(fun e->c.(e)<-c.(e)+1)a;iteri(fun i _->if i<>0then c.(i)<-c.(i)+c.(i-1))c;for i=n-1downto 0do c.(a.(i))<-c.(a.(i))-1;b.(c.(a.(i)))<-a.(i);done;print_int b.(0);for i=1to n-1do print_string" ";print_int b.(i);done;print_newline()

Measured memory_bytes: 36108
n=int(input())
def f(x,y):
  ret=1
  while True:
    if x%2!=y%2:
      return ret
      break
    else:
      x//=2
      y//=2
      ret+=1
for i in range(n-1):
  Ans=[]
  for j in range(n-1-i):
    Ans.append(f(i+1,i+j+2))
  print(*Ans)  
  

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

int main() {
  string a, b, c;
  cin >> a >> b >> c;
  bool ans = (a[a.length()-1] == b[0] &&
	      b[b.length()-1] == c[0]);
  cout << (ans ? "YES" : "NO") << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define mp make_pair
#define REP(i,a,b) for(ll i=a;i<b;i++)
typedef long long ll;
using namespace std;

void FAST() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}


int main(){

FAST();

ll n;
  
  cin>>n;
 ll ans=n+(n*n)+(n*n*n);
 cout<<ans<<endl;



return 0;
}

Measured memory_bytes: 3604
#include<iostream>
#include<vector>
#include<deque>
using namespace std;
const int MAX=1e5+5;
const int inf=100000000;
deque<int>q;
vector<int>e[MAX];
int a[MAX];
int v[MAX];
int book[MAX];
int ans[MAX];
void bfs()
{
	int p;
	while(!q.empty())
	{
		p=q.front();
		q.pop_front();
		for(int i=0;i<a[p];i++)
		{
			if(!book[e[p][i]]){
				if(v[p]+1<v[e[p][i]])
				{
					v[e[p][i]]=v[p]+1;
					ans[e[p][i]]=p;
				}
				book[e[p][i]]=1;
				q.push_back(e[p][i]);
			}
		}
	}
} 
int main()
{
	int n;
	int m;
	cin>>n>>m;
	int hhn,hn;
	for(int i=2;i<=n;i++)
	{
		v[i]=inf,a[i]=0,book[i]=0,ans[i]=0;
	}
	v[1]=0,book[1]=1; 
	for(int i=1;i<=m;i++)
	{
		cin>>hn>>hhn;
		e[hn].push_back(hhn);
		e[hhn].push_back(hn);
		a[hn]++;
		a[hhn]++;
	}
	q.push_back(1);
	bfs();	
	int flag=1;
	for(int i=2;i<=n;i++)
	{
		if(v[i]==inf)
		flag=0;
	}
	if(flag)
	{
		cout<<"Yes"<<endl;
		for(int i=2;i<=n;i++)
		cout<<ans[i]<<endl;
	}else
	cout<<"No"<<endl;

	
	
return 0;
 } 

Measured memory_bytes: 11632
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int x;
	int ans=0;
	int m,d;
	cin>>m>>d;
	for(x=22;x<=d;x++)
	{
		if(x%10>=2)
		{
			if(x%10*(x/10)<=m)
			{
				ans++;
			}
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

/**
 *
 * @author k16075kk
 */
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x, y = 0;
        while (true) {
            x = sc.nextInt();
            y = sc.nextInt();
            if (x == 0 && y == 0) {
                break;
            }
            if (x <= y) {
                System.out.println(x + " " + y);
            } else {
                System.out.println(y + " " + x);
            }
        }
    }
}



Measured memory_bytes: 35748
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		//数取得
		int X = sc.nextInt();
		sc.close();

		int answer = 0;

		if(X <= 599) {
			answer = 8;
		}else if(X <= 799) {
			answer = 7;
		}else if(X <= 999) {
			answer = 6;
		}else if(X <= 1199) {
			answer = 5;
		}else if(X <= 1399) {
			answer = 4;
		}else if(X <= 1599) {
			answer = 3;
		}else if(X <= 1799) {
			answer = 2;
		}else if(X <= 1999) {
			answer = 1;
		}

		System.out.println(answer);
	}

}


Measured memory_bytes: 27084
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<map>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<cctype>
#define pa pair<int,int>
#define INF 0x3f3f3f3f
#define inf 0x3f
#define fi first
#define se second
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define pb push_back

using namespace std;

inline ll read()
{
	long long f=1,sum=0;
	char c=getchar();
	while (!isdigit(c)) {if (c=='-') f=-1;c=getchar();}
	while (isdigit(c)) {sum=sum*10+c-'0';c=getchar();}
	return sum*f;
}
const int MAXN=20;
const int MAXM=(1<<15)+10; 
#define Mod 1000000007
int f[MAXM],P[MAXN];
int e[MAXN];
ll quickpow(ll a,int b)
{
	ll ret=1;
	while (b)
	{
		if (b&1) ret*=a,ret%=Mod;
		b/=2,a*=a,a%=Mod;
	}
	return ret;
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	P[0]=1;
	for (int i=1;i<=n;i++)
		P[i]=(P[i-1]*2)%Mod;
	for (int i=1;i<=m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);u--,v--;
		e[u]|=(1<<v);
	}
	f[0]=1;
	for (int s=1;s<1<<n;s++)
	{
		//if ((s&1)!=((s&2)>>1)) continue;
		if ((s&1)!=(s>>1&1)) continue;
		for (int t=s;t;t=(t-1)&s)
		{
			if ((t&1)!=(t>>1&1)) continue;
			//if ((t&1)!=((t&2)>>1)) continue;
			int tmp=1;
			for (int i=0;i<n;i++)
			{
				if (!(s&(1<<i))) continue;
				if (t&(1<<i)) tmp=1ll*tmp*P[__builtin_popcount(e[i]&(s^t))]%Mod;
				else tmp=1ll*tmp*(P[__builtin_popcount(e[i]&t)]-1)%Mod;
			}
			f[s]+=1ll*tmp*f[s^t]%Mod;
			f[s]%=Mod;
		}
	}
	ll ans=0;
	ans=quickpow(2,m)-f[(1<<n)-1]+Mod;
	ans%=Mod;
	cout<<ans;
	return 0;
}

Measured memory_bytes: 384
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
using ll = long long;
using P = pair<int, int>;

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

char mat[52][52];

int main() {
  int h, w;
  cin >> h >> w;

  for (int i = 0; i < h + 2; i++) {
    mat[i][0] = '.';
    mat[i][w + 1] = '.';
  }
  for (int i = 0; i < w + 2; i++) {
    mat[0][i] = '.';
    mat[h + 1][i] = '.';
  }

  for (int i = 1; i < h + 1; i++) {
    for (int j = 1; j < w + 1; j++) {
      cin >> mat[i][j];
    }
  }

  for (int i = 1; i <= h; i++) {
    for (int j = 1; j <= w; j++) {
      int cnt = 0;
      if (mat[i][j] == '#') {
        cout << '#';
        continue;
      } else {
        rep(k, 8) {
          if (mat[i + dx[k]][j + dy[k]] == '#') {
            cnt++;
          }
        }
        cout << cnt;
      }
    }
    cout << endl;
  }
  return 0;
}


Measured memory_bytes: 3572
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

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


	int X = getint(), Y = getint(), A = getint(), B = getint(), C = getint();

	int abc[400000];
	auto a = abc;
	auto b = abc + A;
	auto c = abc + A + B;

	rep(i, A) a[i] = getint();
	rep(i, B) b[i] = getint();
	rep(i, C) c[i] = getint();

	nth_element(a, b - X, b);
	nth_element(b, c - Y, c);
	memcpy(c + C, b - X, X * sizeof(int));
	nth_element(c - Y, c + C - Y, c + C + X);

	ll kotae = 0;
	for (auto kari = c + C - Y; kari < c + C + X; kari++) kotae += *kari;

	printf("%lld", kotae);

	Would you please return 0;
}

Measured memory_bytes: 1792
{-# LANGUAGE BangPatterns #-}

module Main
  ( main
  )
where
 
import           Control.Applicative
import           Control.Monad
import           Data.Bits
import qualified Data.ByteString.Char8         as BS
import           Data.Char
import           Data.List
import           Data.Maybe
import qualified Data.Vector                   as V
 
parse = fst . fromJust
parseInt = parse . BS.readInt
parseInteger = parse . BS.readInteger
readInt = parseInt <$> BS.getLine
readInteger = parseInteger <$> BS.getLine
readIntList = map parseInt . BS.words <$> BS.getLine

res = 1000000000 + 7

main = do
  n <- readInteger
  print $ foldl1' (\acc i -> (acc * i) `mod` res) [1..n]



Measured memory_bytes: 892
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

struct vec {
    ll x, y;
    vec(ll x, ll y) : x(x), y(y) {}
    vec operator+(const vec& v) const {
        return vec(x + v.x, y + v.y);
    }
    vec operator-(const vec& v) const {
        return vec(x - v.x, y - v.y);
    }

    // 偏角の比較
    bool operator<(const vec &v) const {
        if (*this == v) return false;
        if (y > 0 && v.y > 0) {
            if ((x > 0 && v.x > 0) || (x < 0 && v.x < 0)) return y * v.x < x * v.y;
            if (x <= 0 && v.x >= 0) return false;
            return true;
        }
        else if (y < 0 && v.y < 0) {
            if ((x < 0 && v.x < 0) || (x > 0 && v.x > 0)) return y * v.x < x * v.y;
            if (x >= 0 && v.x <= 0) return false;
            return true;
        }
        else if (y > 0 && v.y < 0) {
            return true;
        }
        else if (y < 0 && v.y > 0) {
            return false;
        }
        else if (y == 0 && x > 0 && (v.y != 0 || (v.y == 0 && v.x < 0))) {
            return true;
        }
        else if (y == 0 && x < 0 && v.y < 0) {
            return true;
        }
        else if (v.y == 0 && v.x < 0 && y > 0) {
            return true;
        }
        else {
            return false;
        }
    }
    friend std::ostream& operator<<(std::ostream &os, const vec &v) {
        return os << "[" << v.x << "," << v.y << "]";
    }
    bool operator==(const vec &v) const {
        return x * v.y == y * v.x && x * v.x >= 0 && y * v.y >= 0;
    }
};

int main() {
    int n; cin >> n;
    vector<vec> p;
    for (int i = 0; i < n; i++) {
        int x, y; cin >> x >> y;
        if (x == 0 && y == 0) continue;
        p.push_back(vec(x, y));
    }
    sort(p.begin(), p.end());
    ll ans = 0;
    for (int i = 0; i < p.size(); i++) {
        vec s(0, 0);
        for (int j = i; j < p.size(); j++) {
            s = s + p[j];
            ans = max(ans, s.x * s.x + s.y * s.y);
        }
        for (int j = 0; j < i; j++) {
            s = s + p[j];
            ans = max(ans, s.x * s.x + s.y * s.y);
        }
    }
    printf("%.15f\n", sqrt(ans));
    return 0;
}

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

using namespace std;

int main(void) {
	int n, m, sum;
	vector<int> v;

	while (cin >> n >> m){
		int digit = 1;
		sum = n + m;
		while (sum /= 10) {
			digit++;
		}
		v.push_back(digit);
	}

	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << endl;
	}

	return 0;
}

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

int main()
{
    int A, B, K;
    cin >> A >> B >> K;
    vector <int> ans;
    for(int i = 0; i <= B; ++i)
    {
        if(i >= A && i < A + K)
        {
            cout << i << endl;
        }
        else if(i > B - K && i >= A)
        {
            cout << i << endl;
        }
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pint = pair<int, int>;
ll N;
const ll INF = 1e12;

int main()
{
    cin >> N;
    ll result = INF;
    for (ll p = 1; p * p <= N; ++p)
    {
        if (N % p == 0)
        {
            ll a = N / p;
            result = min(result, a + p);
        }
    }
    cout << result - 2 << endl;
}

Measured memory_bytes: 256
X = int(input())
def isPrime(n):
	if n == 2:
		return True
	if n % 2 == 0:
		return False
	for i in range(3, int(n**0.5) + 1, 2):
		if n % i == 0:
			return False
	return True
if X == 2:
	print(2)
	exit()
if X % 2 == 0:
	X += 1
while not isPrime(X):
	X += 2
print(X)

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

int main(){
  int n;
  cin>>n;
  fr(i,4) if(n-7*i>=0 && (n-7*i)%4==0){cout<<"Yes"<<endl;return 0;}
  cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define sz(v) (int)(v).size()
using namespace std;
using P = pair<int, int>;
typedef long long ll;
int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	string n;
	cin >> n;
	char last = n[sz(n)-1];
	if (last == '3') cout << "bon" << '\n';
	else if (last == '0' || last == '1' || last == '6' || last == '8') cout << "pon" << '\n';
	else cout << "hon" << '\n';

	return 0;
}


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

const int MaxN = 200000 + 5;

int N;
int A[MaxN];
int Pre[MaxN], Suf[MaxN];

int main() {
  scanf("%d", &N);
  for (int i = 1; i <= N; ++i) scanf("%d", &A[i]);
  for (int i = 1; i <= N; ++i)
    Pre[i] = max(Pre[i - 1], A[i]);
  for (int i = N; i >= 1; --i)
    Suf[i] = max(Suf[i + 1], A[i]);
  for (int i = 1; i <= N; ++i)
    printf("%d\n", max(Pre[i - 1], Suf[i + 1]));
  return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define Abs(x)((x) < 0 ? (x) * -1 : (x))

#define rep(x, y) for ((x) = 0; (x) < (y); (x)++)
#define repin(x, y) for ((x) = 0; (x) <= (y); (x)++)
#define nep(x, y) for ((x) = (y) - 1; 0 <= (x); (x)--)
#define nepi(x, y, z) for ((x) = (y) - 1; (z) <= (x); (x)--)
#define repi(x, y, z) for ((x) = (z); (x) < (y); (x)++)
#define repiin(x, y, z) for ((x) = (z); (x) <= (y); (x)++)
#define reps(x, y, z) for ((x) = 0; (x) < (y); (x) += (z))
#define repis(x, y, z, s) for ((x) = (z); (x) < (y); (x) += (s))
#define repit(x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define nepit(x) for (__typeof((x).rbegin()) it = (x).rbegin(); it != (x).rend(); it++)

#define All(x) (x).begin(),(x).end()

#define Mem0(x) memset(x, 0, sizeof(x))
#define Mem1(x) memset(x, -1, sizeof(x))

#define Unique(v) v.resize(unique(All(v)) - v.begin())

#define peq(p0, p1)(p0.first == p1.first && p0.second == p1.second)

#define End '\n'
#define Out(x) cout<<(x)<<End
#define OutP(p, sep, end) cout<<p.first<<sep<<p.second<<end

template<typename T> inline bool Max(T &x, const T &y) { return x < y ? x = y, 1 : 0; }
template<typename T> inline bool Min(T &x, const T &y) { return x > y ? x = y, 1 : 0; }
template<typename T> using V = vector<T>;
template<typename T> using VV = V<V<T> >;

#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define lb std::lower_bound
#define ub std::upper_bound

#define lbi(v, x) lb(All(v), (x))-v.begin()
#define ubi(v, x) ub(All(v), (x))-v.begin()

static const ll MOD = 1e9 + 7;
static const double PI = 3.141592653589793;

#define LOCAL 0

int main()
{
#if LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("debug.txt", "w", stderr);
#endif

    cin.tie(0);
    ios::sync_with_stdio(false);
	//std::cout.precision(18);

    string s;

	cin >> s;

	int y = (s[0] - '0') * 1000;
	int m = (s[5] - '0') * 10;
	int d = (s[8] - '0') * 10;

	y += (s[1] - '0') * 100;
	y += (s[2] - '0') * 10;
	y += s[3] - '0';

	m += s[6] - '0';

	d += s[9] - '0';

	if (y < 2019) Out("Heisei");
	else if (y == 2019 && m < 4) Out("Heisei");
	else if (y == 2019 && m == 4 && d <= 30) Out("Heisei");
	else Out("TBD");
	
	return 0;
}


Measured memory_bytes: 256
/*in the name of Allah the most beneficent the most merciful.*/
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define MAX 1e18
#define MIN -1e18
#define MOD 1000000007
//#define mod2 20071027
//#define MOD 998244353
#define base 139
// #define MOD 1000074259
#define base2 31
#define memz(a) memset(a, 0, sizeof(a))
#define memn(a) memset(a, -1, sizeof(a))
#define in1(a) scanf("%lld", &a)
#define in2(a, b) scanf("%lld%lld", &a, &b)
#define TC(c) printf("Case #%lld: ", ++c)
#define out(x) cout << #x << " -> " << x << endl;
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
#define FILE   freopen("input.txt", "r", stdin);  freopen("out.txt", "w", stdout);
using namespace std;
const ll B = 20, N = 300010, M = 2000000;
ll n, res;
int solve()
{
	cin >> n;
	if(n%2) printf("0\n");
	else
	{
		ll k = 5;
		n/=2;
		while(k<=n)
		{
			res+=(n/k);
			k*=5;
		}
		printf("%lld\n", res);
	}
	return 0;
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	return solve();
}

Measured memory_bytes: 3748
gN = int(input())
gA = list(map(int,input().split()))

def attack():
    while True:
        minA = min(gA,key=lambda x: float('inf') if x==0 else x)
        maxA = max(gA)
        if minA == maxA:
            return minA

        for a in range(gN):
            if gA[a] == minA: continue
            gA[a] %= minA

if __name__ == "__main__":
    print(attack())


Measured memory_bytes: 14252
/*
Though leaves are many , the root is one.
Through all the lying days of my youth
I swayed my leaves and flowers in the sun.
Now I may wither into the truth.
	  	  	- William Butler Yeats
*/
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
#include<bits/stdc++.h>
#pragma comment("-Wl,--stack=1024000000")
//#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
const int inf=0x3f3f3f3f;
const double eps=1e-6;
const int mod=1000000007;
typedef long long ll;
#ifndef LOCAL
#define cerr if(0)cout
#define eprintf(...) 0
#else
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#endif
inline string getstr(string &s,int l,int r){string ret="";for(int i=l;i<=r;i++)ret.push_back(s[i]);return ret;}
int modpow(int x,int y,int md=mod){int ret=1;do{if(y&1)ret=(ll)ret*x%md;x=(ll)x*x%md;}while(y>>=1);return ret;}
int n;
vector<int>g[200005];
int col[200005],ans[200005];
void dfs(int x,int p){
	for(auto to:g[x])if(to!=p){
		col[to]=col[x]^1;
		dfs(to,x);
	}
}
int main(){
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y;cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(1,-1);
	int sum[2]={};
	for(int i=1;i<=n;i++){
		sum[col[i]]++;
	}
	if(sum[0]>sum[1]){
		swap(sum[0],sum[1]);
		for(int i=1;i<=n;i++)col[i]^=1;
	}
	memset(ans,-1,sizeof ans);
	int hv[3]={n/3,(n+2)/3,(n+1)/3};
	int pos[]={0,0,0};
	if(sum[0]<=n/3){
		for(int i=1;i<=n;i++){
			if(col[i]==0)ans[i]=3,hv[0]--;
		}
		for(int i=1;i<=n;i++){
			if(!~ans[i]){
				if(hv[0])ans[i]=3,hv[0]--;
				else if(hv[1])ans[i]=1,hv[1]--;
				else ans[i]=2,hv[2]--;
			}
		}
		for(int i=1;i<=n;i++){
			cout<<ans[i]+pos[ans[i]]++*3<<" ";
		}
	}else{
		for(int i=1;i<=n;i++){
			if(!hv[col[i]+1])continue;
			ans[i]=col[i]+1;hv[ans[i]]--;
		}
		for(int i=1;i<=n;i++)if(ans[i]==-1)ans[i]=3;
		for(int i=1;i<=n;i++){
			cout<<ans[i]+pos[ans[i]]++*3<<" ";
		}
	}
	return 0;
}

Measured memory_bytes: 19200
#include<bits/stdc++.h>
#define int long long
using namespace std;
int N,M,R;
int p[200][200],r[8],s[8];
int saiki(int u){
	int i,j;
	if(u==R){
		int ans=0;
		for(i=0;i<R-1;i++)
			ans+=p[r[s[i]]][r[s[i+1]]];
		return ans;
	}
	int ans=1919191919419;
	for(i=0;i<R;i++){
		bool f=false;
		for(j=0;j<u;j++)
			if(s[j]==i){
				f=true;
				break;
			}
		if(f)
			continue;
		s[u]=i;
		ans=min(ans,saiki(u+1));
	}
	return ans;
}
signed main(){
	int i,j,k;
	for(i=0;i<200;i++)
		for(j=0;j<200;j++)
			p[i][j]=1919191919419;
	cin>>N>>M>>R;
	for(i=0;i<N;i++)
		p[i][i]=0;
	for(i=0;i<R;i++){
		cin>>r[i];
		r[i]--;
	}
	for(i=0;i<M;i++){
		int u,v,w;
		cin>>u>>v>>w;
		u--;
		v--;
		p[u][v]=w;
		p[v][u]=w;
	}
	for(i=0;i<N;i++)
		for(j=0;j<N;j++)
			for(k=0;k<N;k++)
				p[j][k]=min(p[j][k],p[j][i]+p[i][k]);
	cout<<saiki(0)<<endl;
}

Measured memory_bytes: 512
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
using namespace std;
static const double EPS = 1e-5;
typedef long long ll;


int kousi[21][21];

int main(){
	int N,M;
	
	while(cin>>N){
		if(N==0)break;
		
		memset(kousi,0,sizeof(kousi));
		
		for(int i=0;i<N;i++){
			int x,y;
			cin>>x>>y;
			kousi[x][y]=1;
		}
		
		int M,cx=10,cy=10;
		if(kousi[cx][cy]){
			kousi[cx][cy]=0;
			--N;
		}
		cin>>M;
		for(int i=0;i<M;i++){
			char c;
			int len;
			scanf(" %c %d",&c,&len);
			int dx=0,dy=0;
			switch(c){
			case 'N':
				++dy;
				break;
			case 'E':
				++dx;
				break;
			case 'S':
				--dy;
				break;
			case 'W':
				--dx;
				break;
			}
			
			for(int j=0;j<len;j++){
				cx+=dx;
				cy+=dy;
				if(kousi[cx][cy]){
					kousi[cx][cy]=0;
					--N;
				}
			}
		}
		if(N)puts("No");
		else puts("Yes");
	}
	return 0;
}

Measured memory_bytes: 684
import java.util.Scanner;

public class Main {
	static int n;
	static int m;
	static int[] a;
	static int[] b;
	static boolean[][] graph;
	static boolean[] visited;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		m = in.nextInt();
		a = new int[m];
		b = new int[m];
		graph = new boolean[n][n];
		visited = new boolean[n];
		for (int i = 0; i < m; i++) {
			a[i] = in.nextInt() - 1;
			b[i] = in.nextInt() - 1;
			graph[a[i]][b[i]] = true;
			graph[b[i]][a[i]] = true;
		}
		int ans = 0;
		for (int i = 0; i < m; i++) {
			graph[a[i]][b[i]] = false;
			graph[b[i]][a[i]] = false;
			for (int j = 0; j < n; j++) {
				visited[j] = false;
			}
			dfs(0);
			boolean bridge = false;
			for (int j = 0; j < n; j++) {
				if (visited[j] == false) {
					bridge = true;
				}
			}
			if (bridge) {
				ans++;
			}
			graph[a[i]][b[i]] = graph[b[i]][a[i]] = true;

		}
		System.out.println(ans);
		in.close();
	}

	static void dfs(int v) {
		visited[v] = true;
		for (int i = 0; i < n; i++) {
			if (graph[v][i] == false) {
				continue;
			}
			if (visited[i] == true) {
				continue;
			}
			dfs(i);
		}
	}
}

Measured memory_bytes: 22100
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n; 
  cin >>n;
  priority_queue<int>q;
  for(int i=0;i<n;i++){
    int a;
    cin>>a;
    q.push(a);
  }
  int a,b,amari; 
  while(q.size()>0){
    if(q.size()==1){
      amari=q.top();q.pop();
      break;
    }else if(q.size()==2){
      a=q.top();q.pop();
      b=q.top();q.pop();
      //cout<<a<<" "<<b<<endl;
      a-=b;;
      if(a>0&&b>0){
        q.push(a);
        q.push(b);
      }else{
        amari=b;
      }
    }else{
      a=q.top();q.pop();
      b=q.top();q.pop();
      amari=a%b;
      if(amari!=0)q.push(amari);    
    }
  }
  cout<<amari<<endl;
  return 0;
}


Measured memory_bytes: 892
/*
 * atcoder/abc170/b.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> ostream & operator << (ostream & out, vector<T> const & v) {
  for (auto &&a: v) out << a << " "; out << endl; return out;
}
template <class T> void dump(T &a) { cout << a << endl; }
void solve();
int main() { solve(); return 0; }


void solve() {
  int x, y;
  cin >> x >> y;
  if (y%2==1){
    cout << "No" << endl;
    return;
  }
  int b = (y/2) - x;
  if (b < 0) {
    cout << "No" << endl;
    return;
  }

  int a = 2 * x - (y / 2);
  if (a < 0) {
    cout << "No" << endl;
    return;
  }

  cout << "Yes" << endl;
}


Measured memory_bytes: 3632
#include<stdio.h>

int main(){
    int n,d;
    scanf("%d %d",&n,&d);
    if(n%(2*d+1) == 0){
        printf("%d",n/(2*d+1));
    }else{
        printf("%d",n/(2*d+1)+1);
    }
    return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
int main()
{
	int x,n,i,j,k,flag;
	while(scanf("%d%d",&n,&x)==2&&(n!=0))
	{
		flag=0;
		for(i=1;i<=n-2;i++)
		{
			for(j=2;j<=n-1;j++)
			{
				for(k=3;k<=n;k++)
				{
					if(i==j||i==k||j==k)continue;
					if(i+j+k==x&&i<j&&j<k)
					{
						flag++;
					}
						
				}
			}
		}
		printf("%d\n",flag);
	} 
	return 0;
}


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

int main() {
   vector<int> bingo(9);
   for(int i=0;i<9;i++){
      cin >> bingo.at(i); 
    // cout << bingo.at(i) << endl;
   }
   int N;
   cin >> N;
   vector<int> called(N);
   for(int i=0;i<N;i++){
      cin >> called.at(i); 
     //cout << called.at(i);
   }

   vector<int> open(9);
   for(int i=0;i<9;i++){
      open.at(i) = false;
   }

   for(int i=0;i<N;i++){
      for(int j=0;j<9;j++){
         if(called.at(i) == bingo.at(j)){
            open.at(j) = true;
         }
      }
   }

   
   bool hit;
   hit = false;

   if(open.at(0)&&open.at(1)&&open.at(2)){
      hit = true;
   }else if(open.at(3)&&open.at(4)&&open.at(5)){
      hit = true;
   }else if(open.at(6)&&open.at(7)&&open.at(8)){
      hit = true;
   }else if(open.at(0)&&open.at(3)&&open.at(6)){
      hit = true;
   }else if(open.at(1)&&open.at(4)&&open.at(7)){
      hit = true;
   }else if(open.at(2)&&open.at(5)&&open.at(8)){
      hit = true;
   }else if(open.at(0)&&open.at(4)&&open.at(8)){
      hit = true;
   }else if(open.at(2)&&open.at(4)&&open.at(6)){
      hit = true;
   }


   if(hit){
      cout << "Yes" << endl;
   }else{
      cout << "No" << endl;
   }
   return 0;
}

Measured memory_bytes: 256
import sys
import math
import itertools
import collections

def solve(N,M,X,C,A):
    lis = [i for i in range(N)]
    ans = []
    for k,_ in enumerate(lis,1):
        for c in itertools.combinations(lis,r=k):
            tmp = 0
            dic = {key:0 for key in range(M)}
            for i in set(c):
                tmp += C[i]
                for n,a in enumerate(A[i]):
                    dic[n] += a
            for m in range(M):
                if(dic[m] < X):
                    break
            else:
                ans.append(tmp)
    return min(ans) if(ans != []) else -1
def main():
    N,M,X = map(int,input().split())
    C = []
    A = []
    for _ in range(N):
        tmp = list(map(int,input().split()))
        C.append(tmp.pop(0))
        A.append(tmp)
    # solve()
    print(solve(N,M,X,C,A))

if __name__ == "__main__":
    main()


Measured memory_bytes: 9528
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int, int>pii;
typedef pair<pii, int>pi3;
int mini[1 << 18], maxi[1 << 18];
vector<pii>qs[1000000];
int ans[1000000];
int main()
{
	int num;
	scanf("%d", &num);
	fill(maxi, maxi + (1 << num), 1 << num);
	fill(mini, mini + (1 << num), 1);
	for (int i = 0; i < (1 << num); i++)
	{
		int z;
		scanf("%d", &z);
		if (z > 0)mini[i] = maxi[i] = z;
	}
	for (int i = 0; i < num; i++)
	{
		for (int j = 0; j < (1 << num); j++)
		{
			if (j&(1 << i))maxi[j - (1 << i)] = min(maxi[j - (1 << i)], maxi[j]);
			else mini[j + (1 << i)] = max(mini[j + (1 << i)], mini[j]);
		}
	}
	//for (int i = 0; i < (1 << num); i++)printf("%d %d\n", mini[i], maxi[i]);
	for (int i = 0; i < (1 << num); i++)qs[maxi[i]].push_back(make_pair(mini[i], i));
	priority_queue<pi3>que;
	for (int i = (1 << num); i >= 1; i--)
	{
		for (int j = 0; j < qs[i].size(); j++)
		{
			que.push(make_pair(make_pair(qs[i][j].first, i), qs[i][j].second));
		}
		if (que.empty())
		{
			printf("NO\n");
			return 0;
		}
		pi3 z = que.top();
		que.pop();
		if (!(z.first.first <= i&&i <= z.first.second))
		{
			printf("NO\n");
			return 0;
		}
		ans[z.second] = i;
	}
	printf("YES\n");
	for (int i = 0; i < (1 << num); i++)
	{
		int p = 0;
		for (int j = 0; j < num; j++)if (i&(1 << j))p += 1 << (num - 1 - j);
		printf("%d ", ans[p]);
	}
	printf("\n");
}

Measured memory_bytes: 38272