akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;
import java.util.Arrays;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int list[] = new int[n];
        int sortedList[] = new int[n];

        for (int i = 0; i < n; i++) {
            list[i] = sc.nextInt();
            sortedList[i] = list[i];
        }

        Arrays.sort(sortedList);

        int median_l = sortedList[n / 2 - 1];
        int median_r = sortedList[n / 2];

        for (int i = 0; i < n; i++) {
            if (list[i] > median_l) {
                System.out.println(median_l);
            }
            else {
                System.out.println(median_r);
            }
        }
    }
}


Measured memory_bytes: 91988
#include <stdio.h>
int main(){
  long long int a,b,i,ans;
  scanf("%lld%lld",&a,&b);
  if(a%2==0&&b%2==1)ans=((b-a+1)/2)%2;
  else if(a%2==0&&b%2==0){
    i=((b-a)/2)%2;
    ans=i^b;
  }
  else if(a%2==1&&b%2==1){
    i=((b-a)/2)%2;
    ans=i^a;
  }
  else {
    i=((b-a-1)/2%2);
    ans=a^i;
    ans=ans^b;
  }
  printf("%lld",ans);
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define per(i,a,b) for(int i =(b)-1;i>=(a);--i)
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
typedef vector<int> vi;
const int mod = 1e9 + 7;
const int maxn = 2e6 + 10;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	string s;
	cin >> s;
	cout << (s == "ABC" ? "ARC" : "ABC"); 
	return 0;
}


Measured memory_bytes: 3636
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    long long int n, k;
    cin >> n >> k;
    if(n == 0){
        cout << n << endl;
    }else if(n == k){
        cout << n-k << endl;
    }else if(k > n){
            if(n < -(n-k)){
                cout << n << endl;
            }else{
                cout << -(n-k) << endl;
            }
    }else{
        long long int cnt = n / k;
        n = n - (cnt*k);
            if(n < -(n-k)){
                cout << n << endl;
            }else{
                cout << -(n-k) << endl;
            }
    }
    
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define lld long long
#define pb push_back
#define mk make_pair
#define MAX (lld)1e18+7
#define lim (lld)1e9+7
#define MAX2 (lld)1e5+9
#define ff first
#define ss second
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

const lld mod=lim;
lld ans=0;

void factor(lld n)
{
	lld cnt=0;
	while(n%2==0)
	{
		cnt++;
		n/=2;
	}

	lld temp;
	temp = (lld)sqrt(1+8*cnt);
	temp--;
	temp/=2;
	ans+=floor(temp);


	for(lld i=3;i<=sqrt(n);i+=2)
	{
		cnt=0;
		while(n%i==0)
		{
			cnt++;
			n=n/i;
		}

		temp = (lld)sqrt(1+8*cnt);
		temp--;
		temp/=2;
		ans+=floor(temp);
	}

	cnt=0;

	if(n>2)
		ans+=1;
}

int main()
{
	fastio
	lld n;
	cin>>n;
	factor(n);

	cout<<ans<<endl;

}

Measured memory_bytes: 3664
n,m,x=map(int,input().split())

data=[]

for i in range(n):
    temp=list(map(int,input().split()))
    data.append([temp[0],temp[1:]])

kau=[False]*n

ans=[]

for i in range(2**n):
    check=1
    for j in range(n):
        if((i&check)!=0):
            kau[j]=True
        else:
            kau[j]=False
        check<<=1
    shujuku=[0]*m
    kakaku=0
    for j in range(n):
        if(kau[j]):
            kakaku+=data[j][0]
            for k in range(m):
                shujuku[k]+=data[j][1][k]
    ok=True
    for s in shujuku:
        if(s<x):
            ok=False
    if(ok):
        ans.append(kakaku)

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

Measured memory_bytes: 9268
#include<stdio.h>

int main(void){
int i,k,a[10000];

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

for(k=0;k<=i-1;k++){
printf("Case %d: %d\n",k+1,a[k]);
}

return 0;
}

Measured memory_bytes: 1820
K = int(input())
num = 7
ans = -1

for i in range(1,K+1):
    if num % K == 0:
        ans = i
        break
    num = (num * 10 + 7) % K
#ex.余りの数列を見ると、mod9のとき、7,5,3,1,8...と続く
#この時、(前項*10+7)のmod9を求めていることが分かる。
#1桁上がった値の余りと,同じ値を数列に入れることができるのでこれをループして値の発散を防ぐ。
#ex.77≡5 (mod9) 777≡3 (mod9) 7777≡1 (mod9)
print(ans)

Measured memory_bytes: 9072
/*This Code Is Nude*/
#include <bits/stdc++.h>
 
#define pb push_back
#define ll long long
#define int long long
#define max(a,b) max((long long) a , (long long) b)
#define min(a,b) min((long long) a , (long long) b)

using namespace std;

const int inf = 1e12 + 10; 
const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;
 
bool mark [maxn];
vector<int>adj[maxn];
int a[maxn];

int32_t main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n , m;
	cin >> n >> m;
	int sum = 0 ;
	for(int i = 0 ; i < m ; i ++){
		int x;
		cin >> x;
		sum += x;
	}
	if(sum <= n)
		cout << n - sum << endl;
	else
		cout << -1 << endl;
	return 0;
}


Measured memory_bytes: 8364
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL_DEBUG
  #include "LOCAL_DEBUG.hpp"
#endif
#define int long long

signed main(){

  int n; cin >> n;
  string s; cin >> s;

  vector<char> t(n);
  for(char c1 : {'S','W'}){
    for(char c2 : {'S','W'}){
      t[0] = c1;
      t[1] = c2;
      for(int i = 2; i < n; i++){
        if(s[i-1] == 'o'){
          if(t[i-1] == 'S'){
            if(t[i-2] == 'S') t[i] = 'S';
            else t[i] = 'W';
          }
          else {
            if(t[i-2] == 'S') t[i] = 'W';
            else t[i] = 'S';
          }
        }
        else {
          if(t[i-1] == 'S'){
            if(t[i-2] == 'W') t[i] = 'S';
            else t[i] = 'W';
          }
          else {
            if(t[i-2] == 'W') t[i] = 'W';
            else t[i] = 'S';
          }
        }
      }
      if(s[n-1] == 'o' && (t[n-1] == 'S' && t[n-2] == t[0] || t[n-1] == 'W' && t[n-2] != t[0]) || s[n-1] == 'x' && (t[n-1] == 'S' && t[n-2] != t[0] || t[n-1] == 'W' && t[n-2] == t[0])){
        if(s[0] == 'o' && (t[0] == 'S' && t[n-1] == t[1] || t[0] == 'W' && t[n-1] != t[1])  || s[0] == 'x' && (t[0] == 'S' && t[n-1] != t[1] || t[0] == 'W' && t[n-1] == t[1]) ){
          for(int j = 0; j < n; j++){
            cout << t[j];
          }
          cout << endl;
          return 0;
        }
      }
    }
  }
  cout << -1 << endl;

  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h> 
using namespace std;
const int maxn=1e5+5;
const long long sg=1e10;
long long a,b,c,d,e,f,g,n,m,i,j,sdg[maxn],lili,t;
long long  x[maxn][10],z[maxn],v[101][101],h[maxn];
string p[maxn],s[maxn];
queue<int>q;
bool mark[maxn];
vector<long long> o[maxn],sgd;
map<long long,long long> mp;
char l[10][10],y;
int main(){
ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0);
cin>>a;
for(i=0;i<a;i++){
	cin>>z[i];
	mp[z[i]]=i;
}
sort(z,z+a);
b=0;
for(i=0;i<a;i++){
	if(i%2!=mp[z[i]]%2){
		b++;
	}
}
cout<<b/2<<endl;
return 0;}


Measured memory_bytes: 12672
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <cstring>
typedef long long ll;
using namespace std;

int main()
{
    int n,m;
    cin>>n>>m;
    
    while(n>=2)
    {
        vector<int>s;
        int a;
        for(int i=0;i<n;i++)
        {cin>>a;
        s.push_back(a);}
        int sum=0;
        int max=0;
        for(int i=0;i<n;i++)
            for(int j=i+1;j<n;j++)
            {
                sum=s[i]+s[j];
                if(sum>max &&sum<=m)
                    max=sum;
            }
        if(max==0)
            cout<<"NONE"<<endl;
        else
            cout<<max<<endl;
        cin>>n>>m;
    }
    return 0;
}



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

#define REP(i,n) for(int i=0,_n=(int)(n); i < _n; i++)
typedef long long ll;


bool check(vector<int> P, vector<int> a, vector<int> b) {
  int N = (int)a.size();
  vector<pair<int,int>> vv;
  REP(i, N) {
    vv.emplace_back(a[i] + b[i], i+1);
  }
  sort(vv.begin(), vv.end());

  bool ok = true;
  REP(i, N) {
    if (P[i] != vv[i].second) ok = false;
  }
  if (ok) cout << "OK" << endl; else cout << "    -----  NG ----- " << endl;
  return ok;
}

void print(vector<int> v) {
  REP(i, v.size()) {
    if (i > 0) cout << " ";
    cout << v[i];
  }
  cout << endl;
}

int main2() {
  int N; cin >> N;
  vector<int> P(N);
  REP(i, N) cin >> P[i];

  vector<int> a(N), b(N);
  REP(i, N) {
    a[i] = 30000 * (i + 1);
    b[i] = 30000 * (N - i);
  }
  REP(i, N) {
    b[P[i]-1] += (i+1);
  }
  // check(P, a, b);
  print(a);
  print(b);

  return 0;
}

int main() {
  while (!cin.eof()) {
    main2();
    cin >> ws;
  }
  return 0;
}


Measured memory_bytes: 896
import java.util.Scanner;

class Main
{
	public static void main(String args[])
	{
		Scanner sc = new Scanner(System.in);
		
		int figer[][][] = {
			{//A
				{1,1},
				{1,1},
			},
			{//B
				{1},
				{1},
				{1},
				{1},
			},
			{//C
				{1,1,1,1},
			},
			{//D
				{0,1},
				{1,1},
				{1,0},
			},
			{//E
				{1,1,0},
				{0,1,1},
			},
			{//F
				{1,0},
				{1,1},
				{0,1},
			},
			{//G
				{0,1,1},
				{1,1,0},
			},
		};
		
		int map[][] = new int[8][8];
		
		while (true)
		{
			try
			{
				for (int i = 0; i < 8; i++)
				{
					String str = sc.nextLine();
					for (int j = 0; j < 8; j++)
					{
						map[i][j] = str.charAt(j) - '0';
					}
				}
				
				LOOP1: for (int i = 0; i < figer.length; i++)
				{
					LOOP2: for (int j = 0; j < map.length; j++)
					{
						LOOP3: for (int k = 0; k < map[j].length; k++)
						{
							LOOP4: for (int l = 0; l < figer[i].length; l++)
							{
								LOOP5: for (int m = 0; m < figer[i][l].length; m++)
								{
									try
									{
										if (map[j + l][k + m] != figer[i][l][m])
										{
											continue LOOP3;
										}
										else if (l == figer[i].length-1 && m == figer[i][l].length-1)
										{
											System.out.println((char) (i + 'A'));
											break LOOP1;
										}
									}
									catch (ArrayIndexOutOfBoundsException ae)
									{
										continue LOOP4;
									}
								}
							}
						}
					}
				}
				
				sc.nextLine();
			}
			catch (Exception e)
			{
				break;
			}
		}
	}
}

Measured memory_bytes: 12000
using System;


class Program
{
	static double sin60;
	static double cos60;

	static void Main(string[] args)
	{
		int n = int.Parse(Console.ReadLine());

		double ang = 60 * (Math.PI / 180);
		sin60 = Math.Sin(ang);
		cos60 = Math.Cos(ang);

		Console.WriteLine(0 + " " + 0);
		KochCurve(n, 0, 0, 100, 0);
		Console.WriteLine(100 + " " + 0);
	}

	static void KochCurve(int n, double x0, double y0, double x1, double y1)
	{
		if (n == 0)
		{
			return;
		}
		
		double sx = (2 * x0 + x1) / 3;
		double sy = (2 * y0 + y1) / 3;

		double tx = (x0 + 2 * x1) / 3;
		double ty = (y0 + 2 * y1) / 3;

		double ux = (tx - sx) * cos60 - (ty - sy) * sin60 + sx;
		double uy = (tx - sx) * sin60 + (ty - sy) * cos60 + sy;

		double d = Math.Sqrt((x1 - x0)*(x1 - x0) + (y1 - y0)*(y1 - y0));
		
		KochCurve(n-1, x0, y0, sx, sy);
		Console.WriteLine(sx + " " + sy);

		KochCurve(n-1, sx, sy, ux, uy);
		Console.WriteLine(ux + " " + uy);

		KochCurve(n-1, ux, uy, tx, ty);
		Console.WriteLine(tx + " " + ty);

		KochCurve(n-1, tx, ty, x1, y1);
	}
}



Measured memory_bytes: 15860
#include<iostream>
using namespace std;
static const int MAX = 100;
static const int INFTY = (1<<21);
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

struct Node{int color, dist, parent;};

int M[MAX][MAX], n;
Node node[MAX];

int main(){
  cin >> n;

  //initialize M and node
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      M[i][j] = INFTY;
    }
    node[i].color = WHITE;
    node[i].dist = INFTY;
    node[i].parent = -1;
  }

  //input distances
  for(int i = 0; i < n; i++){
    int u, k, v, c;
    cin >> u >> k;
    while(k--){
      cin >> v >> c;
      M[u][v] = c;
    }
  }

  int p = 0, min_dis;
  node[p].dist = 0;
  node[p].color = BLACK;

  while(true){
    for(int i = 0; i < n; i++){
      if(M[p][i] != INFTY && node[i].color != BLACK){
        int d = node[p].dist + M[p][i];
        if(node[i].dist > d){
          node[i].dist = d;
          node[i].color = GRAY;
          node[i].parent = p;
        }
      }
    }

    p = -1;
    min_dis = INFTY;
    for(int i = 0; i < n; i++){
      if(node[i].color == GRAY && node[i].dist < min_dis){
        p = i;
        min_dis = node[i].dist;
      }
    }

    if(p == -1)
      break;

    node[p].color = BLACK;
  }

  for(int i = 0; i < n; i++){
    cout << i << " " << node[i].dist << endl;
  }
}

Measured memory_bytes: 1200
import java.io.*;
import java.util.Scanner;

public class Main{
    public static void main(String[] args) throws IOException
    {
        Scanner scanner = new Scanner(System.in);

        while(true){
           String line,line2;
           double m,a,disp,val;
           disp = 0;
           int sum=0;
           int s[]= new int[1000];
            line = scanner.next();
            int n = Integer.parseInt(line);

            if(n ==0){
                break;
            }

            
            for(int i =0;i < n;i++){
                line2 = scanner.next();
                s[i]= Integer.parseInt(line2);
                sum = sum + s[i];  
            }
            m = (double)sum/(double)n;
            for(int i = 0; i < n;i++){
                a = (s[i]-m)*(s[i]-m);
                disp = a+disp;
            }
            disp = disp/(double)n;
            val = Math.sqrt(disp);
            System.out.printf("%f\n",val);
            
        }

        }
    }





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

using namespace std;

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

	int n;
	cin >> n;
	vector<long long> a(n);
	for(auto & i : a) cin >> i;
	sort(a.begin(), a.end());
	if (a[0] == 0) cout << 0;
	else {
		long double x = 1;
		for(auto i : a) {
			x *= i;
			if (x > 1e18) {
				cout << -1;
				return 0;
			}
		}
		cout << (long long)x;
	}
}

Measured memory_bytes: 3988
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;
#define Mod 1000000007
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<ll>; using VVI = vector<VI>; using VVVI = vector<VVI>;
#define INF 1234567890


int main(){
    ll i,j;
	ll n;
	cin>>n;
	ll ans=0;
	ll a[n],b[n],c[n-1];
	for(i=0;i<n;i++){
		cin>>a[i];
	}
	for(i=0;i<n;i++){
		cin>>b[i];
		ans+=b[i];
	}
	for(i=0;i<n-1;i++){
		cin>>c[i];
	}

	for(i=0;i<n-1;i++){
		if(a[i]+1==a[i+1]) ans+=c[a[i]-1];
	}

	cout<<ans<<endl;

    
    return 0;
}

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

int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}

int main(){
    string str;
    cin >> str;
    int str_len=str.length();
    int result=0;
    bool check=true;
    if (str[0] == '1'){
        check=false;
    }
    for(int i=1;i<str_len;i++){
        //printf("check:%d str[%d]:%d,result:%d\n",(int)check, i, ctoi(str[i]),result);
        if ((int)check!=ctoi(str[i])) result++;
        check=!check;
    }
    cout << result << endl;
}

Measured memory_bytes: 512
n, m, x = map(int, input().split())
c = list()
a = list()
for i in range(n):
  row_input = list(map(int, input().split()))
  c.append(row_input[0])
  a.append(row_input[1:])
inf_value = 2*sum(c)
def check_valid(completed_choice):
  jth_skill = [0]*m
  for i in range(n):
    if completed_choice[i] == 1:
      for j in range(m):
        jth_skill[j] += a[i][j]
  return all(value>=x for value in jth_skill)
def choose_next_row(partial_choice):
  if len(partial_choice) == n:
    if check_valid(partial_choice):
      return sum(include*cost for include, cost in zip(partial_choice, c))
    else:
      return inf_value
  return min(choose_next_row(partial_choice+[0]), choose_next_row(partial_choice+[1]))
ans = choose_next_row([])
if ans == inf_value:
  print(-1)
else:
  print(ans)

Measured memory_bytes: 9248
#include <bits/stdc++.h>
#define rep3(i, s, n, a) for (int i = (s); i < (int)(n); i += a)
#define rep2(i, s, n) rep3(i, s, n, 1)
#define rep(i, n) rep2(i, 0, n)

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

int main(){
    int k;
    cin >> k;
    int ten=7, now=ten%k;
    bool flag=true;
    rep(i, k){
        // cout << now << endl;
        if(now==0){
            cout << i+1 << endl;
            flag=false;
            break;
        }else{
            ten = ten * 10 % k;
            now = (now + ten) % k;
        }
    }
    if(flag){
        cout << -1 << endl;
    }
    return 0;
}

Measured memory_bytes: 3620
#include <iostream>
using namespace std;
typedef long long int ll;
#define rep(i,m,n) for(ll i=m; i<n; i++)
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string a,b;
    ll m,n;
    cin>>a>>b;
    cin>>m>>n;
    string c;
    cin>>c;
    if(c==a){
    	m--;
    	cout<<m<<" "<<n<<"\n";
    }
    else{
    	n--;
    	cout<<m<<" "<<n<<"\n";
    }
}

Measured memory_bytes: 256
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define FASTIO
#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

#ifdef FASTIO
#define scanf abacaba
#define printf abacaba
#endif

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

using namespace std;


/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/

const int MAXN = 5100;
const ll INF = 1e18;

int n;
ll a[MAXN];

vector<int> eds[MAXN];
int was[MAXN];

array<vector<ll>, 2> dfs1(int v) {
	was[v] = 1;
	array<vector<ll>, 2> cur;
	if (a[v] < 0)
		cur[0].push_back(INF), cur[1].push_back(a[v]);
	else
		cur[0].push_back(a[v]), cur[1].push_back(a[v]);
	for (int u: eds[v]) {
		if (was[u])
			continue;
		auto tmp = dfs1(u);
		array<vector<ll>, 2> tmp2;
		tmp2[0].resize(cur[0].size() - 1 + tmp[0].size() - 1 + 1, INF);
		tmp2[1].resize(cur[0].size() - 1 + tmp[0].size() - 1 + 1, INF);
		for (int i = 0; i < cur[0].size(); ++i)
			for (int j = 0; j < tmp[0].size(); ++j) {
				tmp2[0][i + j] = min(tmp2[0][i + j], cur[0][i] + tmp[0][j]);
				tmp2[1][i + j] = min(tmp2[1][i + j], cur[1][i] + tmp[1][j]);
			}
		cur = tmp2;
	}
	cur[0].push_back(INF);
	cur[1].push_back(INF);
	for (int i = 0; i + 1 < cur[0].size(); ++i) {
		if (cur[0][i] < INF)
			cur[0][i + 1] = min(cur[0][i + 1], 0ll);
		if (cur[1][i] < 0)
			cur[0][i + 1] = min(cur[0][i + 1], 0ll);
	}
	for (int i = 0; i < cur[0].size(); ++i)
		cur[1][i] = min(cur[1][i], cur[0][i]);
	return cur;
}

int main() {
#ifdef FASTIO
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#endif
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	for (int i = 0; i < n - 1; ++i) {
		int a, b;
		cin >> a >> b;
		--a, --b;
		eds[a].push_back(b);
		eds[b].push_back(a);
	}
	auto go = dfs1(0);
	int ans = n;
	for (int i = 0; i < go[0].size(); ++i)
		if (go[0][i] < INF || go[1][i] < 0)
			ans = min(ans, i + 1);
	cout << ans - 1 << "\n";
	return 0;
}




Measured memory_bytes: 1816
#include <bits/stdc++.h>
     
    using namespace std;
     
    int n,W;
    vector<long long> w(101),v(101);
     
    long long tb[100][100001];
     
    long long dp(int i, int weight){
    	if(weight > W) return -1000000000000LL;
    	if(i >= n) {
    		return 0;
    	}
    	
    	if(tb[i][weight] != -1) return tb[i][weight];
    	
    	return tb[i][weight] = max(dp(i+1, weight), dp(i+1, weight+w[i])+v[i] );
    }
     
    int main(){
    	ios_base::sync_with_stdio(false);
    	cin.tie(NULL);
    	
    	memset(tb, -1, sizeof(tb));
    	
    	cin >> n >> W;
    	
    	for(int i = 0; i < n; ++i){
    		cin >> w[i] >> v[i];
    	}
    	
    	cout << dp(0,0) << endl;
    	
    	return 0;
    }

Measured memory_bytes: 78336
//
//  main.cpp
//  ALDS65
//
#include <iostream>
#include <vector>
using namespace std;

int main(int argc, const char * argv[]) {
    // insert code here...
    int N;
    cin >> N;
    vector<int>A(N);
    for (int i=0; i<N; i++) {
        cin >> A.at(i);
    }
    int count=0;
    for (int i=0; i<N; i++) {
        int min=1000000000;
        int min_pos=0;
        for (int j=i; j<N; j++) {
            if (A.at(j)<min) {
                min=A.at(j);// 残りの中で最小の値
                min_pos=j; // 最小の値の場所
            }
        }
        if (min_pos!=i) { // 数字の場所を入れ替える
            A.at(min_pos)=A.at(i);
            A.at(i)=min;
            count++;
        }
    }
    for (int k=0; k<N; k++) {
        if(k>0){
            cout << " ";
        }
        cout << A.at(k);
    }
    cout << endl;
    cout << count << endl;
    return 0;
    /*
     6
     5 6 4 2 1 3
     */
}



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

using ll = long long;
using ld = long double;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define FORR(i, m, n) for (int i = (m); i >= (n); i--)
#define REP(i, n) FOR(i, 0, (n))
#define REPR(i, n) FORR(i, (n) - 1, 0)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define REPS(c, s) for (char c : s)
#define ALL(c) (c).begin(), (c).end()
#define sz(v) (int)v.size()
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000001000000001LL;
const char EOL = '\n';

void solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(numeric_limits<double>::max_digits10);
    solve();
    return 0;
}

template<typename T> vector<vector<T>> pre_warshall_floyd(int n, T inf) {
    vector<vector<T>> g(n, vector<T>(n, inf));
    REP(i, n) g[i][i] = 0;
    return g;
}

template<typename T> vector<vector<bool>> warshall_floyd(vector<vector<T>>& g) {
    int n = sz(g);
    vector<vector<bool>> needless(n, vector<bool>(n, false));
    REP(k, n) REP(i, n) REP(j, n) {
        chmin(g[i][j] ,g[i][k] + g[k][j]);
        if (g[i][j] == g[i][k] + g[k][j] && i != k && k != j) needless[i][j] = true;
    }
    return needless;
}

void solve() {
    int n;
    cin >> n;
    vector<vector<ll>> g = pre_warshall_floyd(n, LINF);
    ll a;
    REP(i, n) REP(j, n) {
        cin >> a;
        if (i == j) continue;
        g[i][j] = a;
    }

    vector<vector<ll>> org = g;
    vector<vector<bool>> needless = warshall_floyd(g);

    ll ans = 0;
    REP(i, n) REP(j, n) {
        if (g[i][j] != org[i][j]) {
            cout << -1 << EOL;
            return;
        }
        if (!needless[i][j]) ans += g[i][j];
    }

    cout << ans / 2 << EOL; 
}



Measured memory_bytes: 1664
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
   
    ll n; 
    cin>>n;
    int ans= n + (n*n)+(n*n*n);
    cout<<ans;
    return 0;
}

Measured memory_bytes: 3644
#define STOPIT
#include <bits/stdc++.h>
#define loop(n) for (lint ngtkana_is_a_genius = 0; ngtkana_is_a_genius < lint(n); ngtkana_is_a_genius++)
#define rep(i, begin, end) for (lint i = lint(begin); (i) < lint(end); i++)
#define all(v) v.begin(), v.end()
#define rand(l, r) std::uniform_int_distribution<>(l, r)(mt)
using lint = long long;
auto mt = std::mt19937_64(std::random_device{}());
auto cmn = [](auto&& a, auto b){ if (a > b) {a = b; return true;} return false; };
auto cmx = [](auto&& a, auto b){ if (a < b) {a = b; return true;} return false; };
void debug_impl() { std::cerr << std::endl; }
template <typename Head, typename... Tail>
void debug_impl(Head head, Tail... tail) { std::cerr << " " << head; debug_impl(tail...); }
#ifndef STOPIT
#define debug(...)\
  do {\
    std::cerr << std::boolalpha << "[" << #__VA_ARGS__ << "]:";\
    debug_impl(__VA_ARGS__);\
    std::cerr << std::noboolalpha;\
  } while (false)
#else
#define debug(...) {}
#endif

template < typename Container, typename Value = typename Container::value_type, std::enable_if_t<!std::is_same< Container, std::string >::value, std::nullptr_t> = nullptr>
std::istream& operator>> (std::istream& is, Container& v)
  { for (auto & x : v) { is >> x; } return is; }

template < typename Container, typename Value = typename Container::value_type, std::enable_if_t<!std::is_same< Container, std::string >::value, std::nullptr_t> = nullptr >
std::ostream& operator<< (std::ostream& os, Container const& v) {
 os << "{";
  for (auto it = v.begin(); it != v.end(); it++)
    {os << (it != v.begin() ? "," : "") << *it;}
  return os << "}";
}

int main() {
  std::cin.tie(0); std::cin.sync_with_stdio(false);
  lint base = 10;
  auto digit_sum = [&] (lint k) {
    lint ans = 0;
    loop(k) {
      ans += k%base;
      k /= base;
    }
    return ans;
  };

  auto generate = [&] (lint i) {
    lint I = 1;
    loop(i) I *= 10;
    std::vector<lint> ans;
    rep(y,0,I*100) {
      if ((y-digit_sum(y))*I > -I + 1 + 9*i*I) break;
      if (y%base==base-1) continue;
      ans.emplace_back(y);
    }
    for (lint & x : ans) {
      x = (x+1) * I - 1;
    }
    return ans;
  };
  std::vector<lint> ans;
  rep(i,0,16) {
    auto v = generate(i);
    ans.insert(ans.end(), all(v));
  }
  std::sort(all(ans));
  ans.erase(ans.begin());

  #ifndef STOPIT
    std::vector<std::vector<lint>> b(18);
    for (lint x : ans) {
      b.at(std::to_string(x).length()).emplace_back(x);
    }
    for (auto&& v : b) {
      debug(v.size(), v);
    }
  #endif

  int k; std::cin >> k;
  rep(i,0,k) {
    std::cout << ans.at(i) << std::endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
int main(){
    string S;cin>>S;
    ll Q;cin>>Q;
    bool flag=0;
    vector<char> f,b;
    rep(i,Q){
        ll T;cin>>T;
        if(T==1){
            flag=(!flag);
        }
        else{
            ll F;char c;cin>>F>>c;
            if(F==1){
                if(flag){
                    b.push_back(c);
                }
                else{
                    f.push_back(c);
                }
            }
            else{
                if(flag){
                    f.push_back(c);
                }
                else{
                    b.push_back(c);
                }
            }
        }
    }
    if(flag){
        reverse(all(S)),reverse(all(b));
        for(auto p:b)cout<<p;
        cout<<S;
        for(auto p:f)cout<<p;
        cout<<endl;
    }
    else{
        reverse(all(f));
        for(auto p:f)cout<<p;
        cout<<S;
        for(auto p:b)cout<<p;
        cout<<endl;
    }
    return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;
import java.util.TreeMap;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		String sentence = "";
		while(sc.hasNext()) {
			sentence += sc.nextLine();
		}

		// アルファベット数格納用
		TreeMap<Character, Integer> countAlph = new TreeMap<>();
		char alphabet = 'a';
		final int ALPHABET_SIZE = 'z' - 'a';
		for(int i=0; i<=ALPHABET_SIZE; i++) {
			countAlph.put(alphabet, 0);
			alphabet++;
		}

		// debug
//		alphabet = 'a';
//		for(int i=0; i<=ALPHABET_SIZE; i++) {
//			System.out.println(String.valueOf(alphabet) + " : " + countAlph.get(alphabet));
//			alphabet++;
//		}

		// アルファベットの数を数える
//		System.out.println(sentence.length());

		for(int i=0; i<sentence.length(); i++) {
			if(sentence.charAt(i) == ' ') continue;
			String checkChar = String.valueOf(sentence.charAt(i));
//			System.out.print(checkChar + ", ");
			if(Character.isUpperCase(checkChar.charAt(0))) checkChar = checkChar.toLowerCase();
			// えいじかどうかのはんてい
			Pattern p = Pattern.compile("[a-z]");
			Matcher m = p.matcher(checkChar);
			if(m.find()) countAlph.put(checkChar.toCharArray()[0], countAlph.get(checkChar.toCharArray()[0]) + 1);
		}

		// 出力
		alphabet = 'a';
		for(int i=0; i<=ALPHABET_SIZE; i++) {
			System.out.println(String.valueOf(alphabet) + " : " + countAlph.get(alphabet));
			alphabet++;
		}

		sc.close();

	}

}


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

int main(){
    int n;
    cin >> n;
    ll ans = 0;
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        ans += a - 1;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int llint;
typedef long int lint;
typedef vector<char> vchar;
typedef vector<int> vint;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
typedef vector<vector<int>> vvint;
typedef vector<vector<char>> vvchar;
#define vsort(v) sort((v).begin(), (v).end())
#define vrsort(v) sort((v).rbegin(), (v).rend())
#define vreverse(v) reverse((v).begin(), (v).end())
#define pb(a) push_back(a)
#define INF 2000000009
#define MOD 1000000007
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  //input
  double w,h,i,x,y;cin>>w>>h>>x>>y;
  //caricurat
  //output
  cout<<std::setprecision(5)<<(w*h/2)<<" ";
  if((x*2==w)&&(y*2==h)){cout<<1<<endl;}
  else{cout<<0<<endl;}
}

Measured memory_bytes: 256
a = []
while True:
    inp = input().split()
    if len(inp) == 3:
        a.append([int(x) for x in inp])
    else:
        break
n = int(inp[0])
bingo = [[False for _ in range(3)] for __ in range(3)]
for _ in range(n):
    b = int(input())
    for i in range(3):
        if b in a[i]:
            bingo[i][a[i].index(b)] = True
ans = "No"
for i in range(3):
    if bingo[i][0] == bingo[i][1] == bingo[i][2] == True:
        ans = "Yes"
    if bingo[0][i] == bingo[1][i] == bingo[2][i] == True:
        ans = "Yes"
if bingo[0][0] == bingo[1][1] == bingo[2][2] == True or bingo[0][2] == bingo[1][1] == bingo[2][0] == True:
    ans = "Yes"
print(ans)


Measured memory_bytes: 3064
#include <stdio.h>
int dp[1000001];
void solve() {
	int i;
	for(i = 0; i < 1000001; ++ i) dp[i] = 0;
	dp[1] = 1;
	for(i = 0; i <= 500000; ++ i) {
		if(i * 2 < 1000001) dp[i * 2] = dp[i];
		if(i * 3 < 1000001) dp[i * 3] = dp[i];
		if(i * 5 < 1000001) dp[i * 5] = dp[i];
	}
}
int main() {
	int i, sum, M, N;
	solve();
	while(1) {
		scanf("%d", &M);
		if(M == 0) break;
		scanf("%d", &N);
		sum = 0;
		for(i = M; i <= N; ++ i) sum += dp[i];
		printf("%d\n", sum);
	}
	return 0;
}

Measured memory_bytes: 4504
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <bitset>
#include <numeric>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
clock_t __my_start_clock = clock();
#else
#define eprintf(...)
#endif

#define TIMESTAMP(x) eprintf("["#x"] Time : %.3lf s.\n", (clock() - __my_start_clock)*1.0/CLOCKS_PER_SEC)
#define TIMESTAMPf(x,...) eprintf("[" x "] Time : %.3lf s.\n", __VA_ARGS__, (clock() - __my_start_clock)*1.0/CLOCKS_PER_SEC)

using namespace std;

#ifdef LOCAL
static struct __timestamper {
  string what;
  __timestamper(const char* what) : what(what){};
  __timestamper(const string& what) : what(what){};
  ~__timestamper(){
    TIMESTAMPf("%s", what.data());
	}
} __TIMESTAMPER("end");
#else 
struct __timestamper {};
#endif

typedef long long ll;
typedef long double ld;

char s[510000];

int main() {
#ifdef LOCAL
  freopen("a.in", "r", stdin);
  freopen("a.out", "w", stdout);
#endif

  while (scanf("%s", s) == 1) {
    int n = strlen(s) + 1;
    vector<int> v(n);
    for (int i = 0; i < n - 1; i++) {
      if (s[i] == '<') {
        v[i + 1] = v[i] + 1;
      }
    }

    for (int i = n - 2; i >= 0; i--) {
      if (s[i] == '>') {
        v[i] = max(v[i], v[i + 1] + 1);
      }
    }

    ll ans = accumulate(v.begin(), v.end(), 0LL);
    printf("%lld\n", ans);
  }

  return 0;
}


Measured memory_bytes: 2688
def main():
    n,k = map(int,input().split())
    ans = 0
    for i in range(1,n+1):
        c = 0
        while i<k:
            i = i*2
            c += 1
        ans += 1/n * (1/2)**c
    print(ans)

if __name__ == "__main__":
    main()


Measured memory_bytes: 9356
#include <stdio.h>

int main(void) {
    int n, count = 0;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        if(i%2 == 1) {
            count++;
        }
    }
    double m = (double)n;
    double c = (double)count;
    printf("%f\n", c/m);
    return 0;
}

Measured memory_bytes: 128
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 文字列の入力(スペース改行関係なし)
		String s = sc.next() + ".";
      	String t = sc.next();

		if(t.matches(s)){
			// 出力
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}
		
	}
}

Measured memory_bytes: 38368
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define RFOR(i,a,b) for(int i=(b-1); i>=(a); i--)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define pb push_back
using ll = long long;
using D = double;
using LD = long double;
using P = pair<int, int>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main(){
    int n,m; cin >> n >> m;
    n = 2*m+1;
    int l1 = 1, r1 = m, l2 = m+1, r2 = n;
    while(r1 -l1 > 0){
        cout << l1 << " " << r1 << endl;
        l1++; r1--;
    }
    while(r2 - l2 > 0){
        cout << l2 << " " << r2 << endl;
        l2++; r2--;
    }
}


Measured memory_bytes: 3636
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<queue>
using namespace std;
#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
typedef pair<int, int>P;
const int INF = 1e15;
const int MOD = 1e9 + 7;
const double PI = 3.14159265358979323846;

signed main() {
	int M1, D1, M2, D2;
	cin >> M1 >> D1 >> M2 >> D2;
	cout << (M1 != M2);
}

Measured memory_bytes: 256
// 127_C_Prison2.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <algorithm>

using namespace std;

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

	int maxl = 0;
	int minr = n + 1;
	for (int i = 0; i < m; i++)
	{
		int l, r;
		cin >> l >> r;

		maxl = max(l, maxl);
		minr = min(r, minr);
	}

	int answer = 0;
	if (maxl <= minr) answer = minr - (maxl - 1);
	cout << answer << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
	int n, b, f, r, v;
	cin >> n;
	int B[4][3][10] = {{{0}}};
	for(int i=0; i<n; ++i)
	{
		cin >> b >> f >> r >> v;
		B[b-1][f-1][r-1] += v;
	}
	for( b=0; b<4; ++b)
	{
		if(b) cout << "####################" << endl;
		for(f=0; f<3;++f)
		{
			for(r=0;r<10;++r)
				cout << " " << B[b][f][r];
			cout << endl;
		}		
	}
	return 0;
}

Measured memory_bytes: 3104
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int max = 0;
        int sum = 0;

        for (int i = 0; i < n; i++) {
            int tmp = sc.nextInt();
            if (max < tmp) {
                max = tmp;
            }
            sum += tmp;
        }
        sc.close();
        sum -= max / 2;

        System.out.println(sum);

    }
}

Measured memory_bytes: 21716
n=int(input())
dis=[list(map(int,input().split())) for _ in range(n)]
c=[[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
  for j in range(n):
    c[i][j]=min(dis[i][k]+dis[k][j] for k in range(n))
for i in range(n):
  for j in range(n):
    if c[i][j]!=dis[i][j]:
      print(-1)
      exit()
for i in range(n):
  for j in range(n):
    for k in range(n):
      if i==k or j==k:continue
      if dis[i][j]==dis[i][k]+dis[k][j]:c[i][j]=0
print(sum(sum(c[i]) for i in range(n))//2)

Measured memory_bytes: 76248
#include<iostream>
using namespace std;
static const int MAX=100;
static const int INFTY=(1<<21);
static const int WHITE=0;
static const int GRAY=1;
static const int BLACK=2;

int n,m[MAX][MAX];

int prim(){
  int u,minv;
  int d[MAX],p[MAX],color[MAX];

  for(int i=0;i<n;i++){
    d[i]=INFTY;
    p[i]=-1;
    color[i]=WHITE;
  }

  d[0]=0;

  while(1){
    minv=INFTY;
    u=-1;
    for(int i=0;i<n;i++){
      if(minv>d[i]&&color[i]!=BLACK){
        u=i;
        minv=d[i];
      }
    }
    if(u==-1) break;
    color[u]=BLACK;
    for(int v=0;v<n;v++){
      if(color[v]!=BLACK&&m[u][v]!=INFTY){
        if(d[v]>m[u][v]){
          d[v]=m[u][v];
          p[v]=u;
          color[v]=GRAY;
        }
      }
    }
  }
  int sum=0;
  for(int i=0;i<n;i++){
    if(p[i]!=-1) sum+=m[i][p[i]];
  }
  return sum;
}

int main(){
  cin>>n;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      int e;
      cin>>e;
      m[i][j]=(e==-1)?INFTY:e;
    }
  }
  cout<<prim()<<endl;

  return 0;
}



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

void print_array(int *A, int N){
  printf("%d", A[0]);
  for(int i = 1; i < N; ++i)
  {
    printf(" %d", A[i]);
  }
  printf("\n");
}

int main()
{
  int i, j, k, v, N;
  int A[100+5];
  scanf("%d", &N);

  for(i = 0; i < N; ++i)
  {
    scanf("%d", &A[i]);
  }
  print_array(A, N);

  for(i = 1; i < N; ++i)
  {
    v = A[i];
    j = i - 1;
    while(j>=0 && A[j] > v)
    {
      A[j+1] = A[j];
      --j;
    }
    A[j+1] = v;
    print_array(A, N);
  }

  return 0;
}


Measured memory_bytes: 3228
n=int(input())
l=map(int,input().split())
x,y,z=0,0,0
for a in l:
    if a%4==0:
        z+=1
    elif a%2==0:
        y+=1
    else:
        x+=1
if y>0:
    x+=1
print('Yes'if x<=z+1 else'No')


Measured memory_bytes: 16924
#include<bits/stdc++.h>
#define ll long long

using namespace std;

int main()
{
	string input;
	cin>>input;
	queue<pair <char , int > > q;
	map <char , int> cnt;
	for(int i = 0 ; i < input.size() ; i++)
	{
		cnt[input[i]]++;
	}	
	bool valid = 1;
	if(abs(cnt['a'] - cnt['b']) >=2 || abs(cnt['c'] - cnt['b']) >=2 || abs(cnt['a'] - cnt['c']) >=2)
	{
		valid = 0;
	}
//	if(temp == ans) valid = 0;
	if(valid) printf("YES\n");
	else
	printf("NO\n");
	return 0;
}

Measured memory_bytes: 512
#include<stdio.h>
int main(void){
  int k,n;
  scanf("%d%d",&k,&n);
  int a[n];
  for(int i=0;i<n;i++){
	scanf("%d",&a[i]);
  }
int d[n],max=0;
  for(int i=0;i<n-1;i++){
	d[i]=a[i+1]-a[i];
    if(d[i]>max)max=d[i];
  }
  d[n-1]=a[0]+k-a[n-1];
  if(d[n-1]>max)max=d[n-1];
  printf("%d",k-max);
  return 0;
}

Measured memory_bytes: 1664
#include <iostream>
#include <list>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
typedef long long lli;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<vector<lli> > mat;
typedef vector<vector<bool> > matb;
typedef vector<string> vst;
typedef pair<lli,lli> pll;
typedef pair<double,double> pdd;

lli n;
mat t;
vll p;
vll sib;
vll d;
vll h;

lli depth(lli x){
    if(d[x] >= 0) return d[x];
    if(p[x] == -1) return d[x] = 0;
    return d[x] = depth(p[x]) + 1;
}

lli height(lli x){
    lli ret = 0;
    if(h[x] >= 0) return h[x];
    for(lli i = 0;i < t[x].size();i++) ret = max(ret,height(t[x][i])+1);
    return h[x] = ret;
}

int main(){
    cin >> n;
    t = mat(n);
    p = vll(n,-1);
    sib = vll(n,-1);
    d = vll(n,-1);
    h = vll(n,-1);
    for(lli i = 0;i < n;i++){
        lli id,left,right;
        cin >> id >> left >> right;
        if(left >= 0){
            t[id].push_back(left);
            sib[left] = right;
            p[left] = id;
        }
        if(right >= 0){
            t[id].push_back(right);
            sib[right] = left;
            p[right] = id;
        }
    }
    for(lli i = 0;i < n;i++){
        cout << "node " << i << ": ";
        cout << "parent = " << p[i] << ", ";
        cout << "sibling = " << sib[i] << ", ";
        cout << "degree = " << t[i].size() << ", "; 
        cout << "depth = " << depth(i) << ", ";
        cout << "height = " << height(i) << ", ";
        if(p[i] == -1) cout << "root";
        else if(t[i].size() == 0) cout << "leaf";
        else cout << "internal node";
        cout << endl;
    }
}

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

using namespace std;

const int N = 3005;
const int mod = 998244353;

int n, s, x, dp[N], ans;

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

    for (int i = 1; i <= n; i++) {
        cin >> x;
        if (x > s) {
            continue;
        }
        if (s == x){
            ans += ((n - i + 1) * i) % mod;
            ans %= mod;
        } else {
            ans += (dp[s - x] * 1ll * (n - i + 1)) % mod;
            ans %= mod;
        }
        for (int j = s; j >= x; j--) {
            dp[j] = (dp[j - x] + dp[j] ) % mod;
        }
        dp[x] = (dp[x] + i) % mod;
    }

    cout << ans << endl;
}


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

int main(){
    int n,k;
    long long h[100005]={};
    long long ans = 1e9+1;
    cin>>n>>k;
    for(int i=0; i<n; i++){
        cin>>h[i];
    }
    sort(h,h+n);

    for(int i=0; i<=n-k; i++){
        if(ans > h[i+k-1] - h[i]){
            ans = h[i + k - 1] - h[i];
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 1024
#include <stdio.h>

#define SIZE 320
#define NUM 640

const int Mod = 998244353;

int main()
{
	int i, N, Q;
	char S[200001];
	scanf("%d %d", &N, &Q);
	
	char block[NUM];
	int j, k, l, r, d, q, n = (N - 1) / SIZE, m = N - n * SIZE, flag[NUM];
	long long ans, ans_block[NUM] = {}, fill_block[10], pow[200001];
	for (i = 1, pow[0] = 1; i < N; i++) pow[i] = pow[i-1] * 10 % Mod;
	for (i = 1; i <= 9; i++) {
		for (j = 1, fill_block[i] = i; j < SIZE; j++) fill_block[i] = (fill_block[i] * 10 + i) % Mod;
	}
	for (i = 0; i <= n; i++) {
		block[i] = 1;
		flag[i] = 1;
		if (i < n) ans_block[i] = fill_block[1] * pow[m+(n-i-1)*SIZE] % Mod;
		if (i == n) for (j = 0, ans_block[i] = 0; i * SIZE + j < N; j++) ans_block[i] = (ans_block[i] * 10 + 1) % Mod;
	}
	
	for (q = 1; q <= Q; q++) {
		scanf("%d %d %d", &l, &r, &d);
		l--;
		r--;
		i = l / SIZE;
		if (flag[i] == 1) {
			for (j = i * SIZE; j < N && j < (i + 1) * SIZE; j++) S[j] = block[i];
			flag[i] = 0;
		}
		for (j = l, i = j / SIZE; j <= r && j < (i + 1) * SIZE; j++) {
			ans_block[i] = (ans_block[i] + pow[N-j-1] * (Mod - S[j]) % Mod + pow[N-j-1] * d) % Mod;
			S[j] = d;
		}
		if (j <= r) {
			for (i++; i < r / SIZE; i++) {
				flag[i] = 1;
				block[i] = d;
				ans_block[i] = fill_block[d] * pow[m+(n-i-1)*SIZE] % Mod;
			}
			if (flag[i] == 1) {
				for (j = i * SIZE; j < N && j < (i + 1) * SIZE; j++) S[j] = block[i];
				flag[i] = 0;
			}
			for (j = i * SIZE; j <= r; j++) {
				ans_block[i] = (ans_block[i] + pow[N-j-1] * (Mod - S[j]) % Mod + pow[N-j-1] * d) % Mod;
				S[j] = d;
			}
		}
		
		for (i = 0, ans = 0; i < n; i++) ans += ans_block[i];
		ans = (ans + ans_block[n]) % Mod;
		printf("%lld\n", ans);
	}
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 4072
import java.util.HashMap;
import java.util.Scanner;
 
class Main {
    void solve() {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < n; i++) {
            int d = in.nextInt();
            if(map.containsKey(new Integer(d))) {
                map.put(new Integer(d), map.get(new Integer(d))  +1);
            }else {
                map.put(new Integer(d), 1);
            }
        }
        int m = in.nextInt();
        for(int i = 0; i < m; i++) {
            int t = in.nextInt();
            if(!map.containsKey(new Integer(t))) {
                System.out.println("NO");
                return;
            }
            int count = map.get(new Integer(t));
            if(count == 0) {
                System.out.println("NO");
                return;
            }
            map.put(new Integer(t), count - 1);
        }
        System.out.println("YES");
    }
 
    public static void main(String[] args) {
        new Main().solve();
    }
}

Measured memory_bytes: 128820
#include <bits/stdc++.h>
using namespace std;
int main() 
{
	int n;
	cin>>n;
	vector<int> height;
	for(int i=0;i<n;i++)
	{
	    int x;
	    cin>>x;
	    height.push_back(x);
	}
	int dp[n+1]={0};
	dp[1]=abs(height[0]-height[1]);
    for(int i=2;i<=n;i++)
    {
        dp[i]=min(dp[i-1]+abs(height[i]-height[i-1]),dp[i-2]+abs(height[i]-height[i-2]));
    }
    cout<<dp[n-1]<<endl;
    //cout<<dp[1];
	return 0;
}

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

using ll = long long int;

typedef pair<int, int> P;

const int MAX = (int)(1e5 + 5);
const ll INF = (ll)(1e10 + 5);

const int MAX_N = (int)(1e5 + 5);

int n;

ll l[MAX_N];
ll r[MAX_N];

pair<ll, ll> p[MAX_N];

ll min_r = INF;
ll max_l = -1L;

inline bool cmp(pair<ll, ll> a, pair<ll, ll> b) {
  return a.first < b.first || (a.first == b.first && a.second > b.second);
}

int main(void) {
  // Here your code !
  scanf("%d", &n);

  for (int i = 0; i < n; ++i) {
    scanf("%lld %lld", &(l[i]), &(r[i]));
    max_l = max(max_l, l[i]);
    min_r = min(min_r, r[i]);
  }

  ll ans = 0L;

  // for case that a part of group is singleton
  for (int i = 0; i < n; ++i) {
    ans = max(ans, max(min_r - max_l + 1, 0LL) + r[i] - l[i] + 1L);
  }

  for (int i = 0; i < n; ++i) {
    p[i].first = max(min_r - l[i] + 1L, 0LL);   // first: fixed right
    p[i].second = max(r[i] - max_l + 1L, 0LL);  // second: fixed left
  }

  sort(p, p + n, cmp);

  for (int i = 1; i < n; ++i) {
    ans = max(ans, p[0].first + p[i].second);
  }

  ll part = p[0].second;
  for (int i = 1; i < n; ++i) {
    ans = max(ans, part + p[i].first);
    part = min(part, p[i].second);
  }

  printf("%lld\n", ans);

  return 0;
}


Measured memory_bytes: 3328
#include <stdio.h>

int rs2as(char);

int main(void) {
	char rs[101];
	int i;
	int as;
	while(1) {
		if(scanf("%s",rs)==-1)break;
		for(i=0;rs[i]!=0;i++);
		i--;
		as=rs2as(rs[i]);
		for(i--;i>=0;i--) {
			if(rs2as(rs[i])<rs2as(rs[i+1]))as-=rs2as(rs[i]);
			else as+=rs2as(rs[i]);
		}
		printf("%d\n",as);
	}
	return 0;
}

int rs2as(char ls) {
	switch(ls) {
		case 'I':return 1;break;
		case 'V':return 5;break;
		case 'X':return 10;break;
		case 'L':return 50;break;
		case 'C':return 100;break;
		case 'D':return 500;break;
		case 'M':return 1000;break;
		default:return 0;break;
	}
	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(signed i=0;i<n;++i)
#define repi(n) rep(i,n)
#define int long long
#define str string
#define vint vector<int>
#define pint pair<int,int>
#define pb(a) push_back(a)
#define all(v) v.begin(),v.end()
#define yn(b) cout<<((b)?"Yes":"No")<<endl
#define YN(b) cout<<((b)?"YES":"NO")<<endl
#define call(a) for(auto t:a)cout<<t<<" ";cout<<endl
#define ENDL printf("\n");
#define debg(a) cout<<#a<<":"<<a<<endl;
#define SORT(a) sort(all(a));
#define INF 1LL<<60
#define inf INF
#define out(i) cout<<i<<endl;
#define allSum(a) accumulate(a.begin(),a.end(),0)
int min(int a,int b){if(a>b)return b;return a;}
int max(int a,int b){if(a>b)return a;return b;}

signed main(){
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  int y3=(c-a)+d;
  int x3=c-(d-b);
  int y4=(c-a)+b;
  int x4=(b-d)+a;
  printf("%lld %lld %lld %lld\n",x3,y3,x4,y4);
  

  return 0;
}



Measured memory_bytes: 256