akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
 
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
 
        int s = sc.nextInt();
        int w = sc.nextInt();
 
 
        if(s > w){
            System.out.println("safe");
        }else{
            System.out.println("unsafe");
        }
 
 
    }
}

Measured memory_bytes: 27032
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define mp make_pair
#define F first
#define S second
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define INF 0x3f3f3f3f
typedef long long ll;
/*while(l<=r)
{
    ll mid=(l+r)/2;
    if(check(mid)) r=mid-1;
    else l=mid+1;
}*/
set<char> s1,s2;

int main()
{
    s1.insert('R');
    s1.insert('U');
    s1.insert('D');
    s2.insert('L');
    s2.insert('U');
    s2.insert('D');
    string s;
    while(cin>>s)
    {
        bool flag=true;
        rep(i,s.size())
        {
            if(i%2==0)
            {
                if(!s1.count(s[i])) flag=false;
            }
            else if(!s2.count(s[i])) flag=false;
         }
         if(flag) cout<<"Yes\n";
         else cout<<"No\n";
    }

    return 0;
}


Measured memory_bytes: 256
MOD=10**9+7
ans=0
N,K=map(int,input().split())
dp=[0]*(K+1)
for i in range(K,0,-1):
	seq=K//i
	seq=pow(seq,N,MOD)
	for j in range(2*i,K+1,i):
		seq=(seq-dp[j])%MOD
	dp[i]=seq
	ans+=(seq*i)%MOD
print(ans%MOD)

Measured memory_bytes: 68952
#include <iostream>
#include <algorithm>

using namespace std;

int n;

int main(){
	cin >> n;
	int i = n;
	int j = 1;
	while (1)
	{
		i = n*j;
		if(i % n == 0 && i % 2 == 0){
			cout << i << endl;
			break;
		}
		j++;
	}
}


Measured memory_bytes: 256
import java.util.*;
class P
{
	int a;
	int b;
	P(int a, int b)
	{
		this.a = a;
		this.b = b;
	}
}
public class Main 
{
	public static void main(String[] args) 
	{
		Scanner stdIn = new Scanner(System.in);
		int w = stdIn.nextInt();
		int n = stdIn.nextInt();
		List<P> list = new ArrayList<P>();
		for(int i = 0; i < n; ++i)
		{
			String[] str = stdIn.next().split(",");
			int a = Integer.parseInt(str[0]);
			int b = Integer.parseInt(str[1]);
			list.add(new P(a, b));
		}
		List<Integer> start = new ArrayList<Integer>();
		for(int i = 0; i < w; ++i)
		{
			start.add(i + 1);
		}
		List<Integer> end = new ArrayList<Integer>();
		for(int i = 0; i < w; ++i)
		{
			end.add(0);
		}
		for(int i = 0; i < w; ++i)
		{
			for(int j = 0; j < n; ++j)
			{
				if(start.get(i) == list.get(j).a)
				{
					start.set(i, list.get(j).b);
				}
				else if(start.get(i) == list.get(j).b)
				{
					start.set(i, list.get(j).a);
				}
			}
			end.set(start.get(i) - 1, i + 1);
		}
		for(int i = 0; i < w; ++i)
		{
			System.out.println(end.get(i));
		}
	}
}

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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int x,a,b; cin>>x>>a>>b;
	cout<<(min(abs(x-a),abs(x-b))==abs(x-a)?'A':'B')<<"\n"s;
}

Measured memory_bytes: 256
#include <cstdio>

using namespace std;

typedef long long ll;

ll n, s;
ll calc(ll a, ll b) {
  ll ret = 0;
  while (a > 0) {
    ret += a%b;
    a /= b;
  }
  return ret;
}

int main(void) {
  scanf("%lld%lld", &n, &s);
  if (n == s) {
    printf("%lld\n", n+1);
    return 0;
  }
  for (ll i = 2; i*i <= n; i++) {
    if (s == calc(n, i)) {
      printf("%lld\n", i);
      return 0;
    }
  }
  ll res = -1;
  for (ll i = 1; i*i <= n; i++) {
    if (s >= i) {
      ll b = (n-(s-i))/i;
      if (b > 1 && calc(n, b) == s) {
        res = b;
      }
    }
  }
  printf("%lld\n", res);
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define FOR(i, n) for(ll i = 0; i < n; i++)
#define FORR(i, n) for(ll i = n; i >= 0; i--)
#define FORS(i, m, n) for(int i = m;i < n;i++)
#define ALL(v) accumulate(v.begin(),v.end(),0)
#define OUT(n) (cout << n << endl)
#define IN1(a) (cin >> a)
#define IN2(a,b) (cin >> a >> b)
#define IN3(a,b,c) (cin >> a >> b >> c)


using namespace std;
typedef long long ll;

int main(){
  ll n;
  IN1(n);
  vector<int>a_array(n - 1);
  ll sum=0;
  FOR(i,n-1){
  cin >> a_array.at(i);
  }
  vector<ll>ans(n);
  FOR(i,(n-1)){
    ans.at(a_array.at(i) - 1) += 1;
  }
  FOR(i,n){
    OUT(ans.at(i));
  }
}

Measured memory_bytes: 5644
from collections import Counter


N, M = [int(x) for x in input().split()]
Cnter = Counter([int(x) for x in input().split()])
for i in range(M):
    b, c = [int(x) for x in input().split()]
    Cnter[c] += b
V = sorted(list(Cnter.most_common()))
cnt = 0
ans = 0
for v in V[::-1]:
    ans += v[0] * min(v[1], N - cnt)
    cnt += v[1]
    if cnt >= N:
        break
print(ans)


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

int main()
{
	int K, S;
	cin >> K >> S;
	int sum = 0;
	for (int X = 0; X < K + 1; X++) {
		for (int Y = 0; Y < K + 1; Y++) {
			if (X + Y <= S && S - X - Y <= K) {
				sum += 1;
			}
		}
	}
	cout << sum << endl;
}

Measured memory_bytes: 256
#include<queue>
#include<cstdio>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

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

class union_find{
	vector<int> a;
public:
	union_find(int n):a(n,-1){}
	int find(int x){
		if(a[x]<0) return x;
		return a[x]=find(a[x]);
	}
	void unite(int x,int y){
		x=find(x),y=find(y);
		if(x!=y){ a[x]+=a[y]; a[y]=x; }
	}
	int size(int x){ return -a[find(x)]; }
};

int w,h,B[12][12];

int nf,f[12][12];
vector<int> next[144];

void dfs(int i,int j,bool vis[12][12]){
	vis[i][j]=true;
	rep(k,4){
		int y=i+dy[k],x=j+dx[k];
		if(0<=y && y<h && 0<=x && x<w){
			if(!vis[y][x] && B[i][j]==B[y][x]){
				dfs(y,x,vis);
			}
			else if(B[i][j]>B[y][x]){
				next[f[i][j]].push_back(f[y][x]);
			}
		}
	}
}

int main(){
	for(;scanf("%d%d",&w,&h),w;){
		int fx,fy,fq; scanf("%d%d%d",&fx,&fy,&fq); fx++; fy++;
		rep(i,h+2) B[i][0]=B[i][w+1]=0;
		rep(j,w+2) B[0][j]=B[h+1][j]=0;
		rep(i,h) rep(j,w) scanf("%d",B[i+1]+j+1);
		h+=2; w+=2;

		union_find U(h*w);
		rep(i,h) rep(j,w) rep(k,4) {
			int y=i+dy[k],x=j+dx[k];
			if(0<=y && y<h && 0<=x && x<w && B[i][j]==B[y][x]) U.unite(i*w+j,y*w+x);
		}

		nf=0;
		int tmp[144];
		rep(u,h*w) tmp[u]=-1;
		rep(i,h) rep(j,w) if(tmp[U.find(i*w+j)]==-1) tmp[U.find(i*w+j)]=nf++;
		rep(i,h) rep(j,w) f[i][j]=tmp[U.find(i*w+j)];

		int hh[144];
		int sz[144];
		rep(i,h) rep(j,w) {
			hh[f[i][j]]=B[i][j];
			sz[f[i][j]]=U.size(i*w+j);
		}

		rep(u,nf) next[u].clear();
		bool vis[12][12]={};
		rep(i,h) rep(j,w) if(!vis[i][j]) dfs(i,j,vis);

		int nq; scanf("%d",&nq);
		while(nq--){
			int qt,qx,qy; scanf("%d%d%d",&qt,&qx,&qy); qx++; qy++;

			int s=f[fy][fx],t=f[qy][qx];
			double water[144]={};
			water[s]=fq*qt;

			priority_queue< pair<int,int> > Q;
			rep(u,nf) Q.push(make_pair(hh[u],u));

			while(!Q.empty()){
				int u=Q.top().second; Q.pop();

				double over=max(water[u]-sz[u]*30*30*30,0.0);
				water[u]=min(water[u],sz[u]*30*30*30.0);

				rep(i,next[u].size()){
					int v=next[u][i];
					water[v]+=over/next[u].size();
				}
			}

			printf("%d\n",(int)(water[t]/(sz[t]*30*30)));
		}
	}

	return 0;
}

Measured memory_bytes: 0
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <bitset>
#include <complex>
using namespace std;
#define REP(i,n) for(int i = 0; i < (int)n; i++)
#define FOR(i,a,b) for(int i = a; i < (int)b; i++)
#define pb push_back
#define mp make_pair
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 1 << 27;
//////////////////////////////
// ????????????
int dx[4] = {0,1,-1,0};
int dy[4] = {-1,0,0,1};
int H[6][6] = {
    {1,5,2,3,0,4}, // North : ?\\????§????   ( y:-1 )
    {3,1,0,5,4,2}, // East  : ???????§????   ( x:+1 )
    {2,1,5,0,4,3}, // West  : ???????§????   ( x:-1 )
    {4,0,2,3,5,1}, // South : ??????????§???? ( y:+1 )
    {0,2,4,1,3,5}, // Right : ?????????????????¢ (?§??????????)
    {0,3,1,4,2,5}  // Left  : ?????????????????¢ (?§??????????)
};
// ???????????????????????????
// d[0] := top,   d[1] := front
// d[2] := right, d[3] := left
// d[4] := back,  d[5] := bottom
enum{TOP, FRONT, RIGHT, LEFT, BACK, BOTTOM};
struct Cube{
    vector<int> d;
    // ???????????????????????§?????????
    Cube(vector<int> v){
        if( v.size() == 6 )
            d = v;
        else
            d = vector<int>(6);
    }
    Cube(){ d = vector<int>(6); }
    // dir?????????????????¢ (????????¨??????)
    Cube roll(int dir){
        vector<int> d_(6);
        for(int i = 0 ; i < 6 ; i++ ){
            d_[i] = d[ H[dir][i] ];
        }
        return Cube(d_);
    }
};
int main() {
	vi v;
	REP(i, 6)
		v.pb(i+1);
	int n;
	while(cin >> n, n) {
		Cube c(v);
		int sum = 1;
		while(n--) {
			string in; cin >> in;
			if(in[0] == 'N')
				c = c.roll(0);
			else if(in[0] == 'S')
				c = c.roll(3);
			else if(in[0] == 'E')
				c = c.roll(1);
			else if(in[0] == 'W')
				c = c.roll(2);
			else if(in[0] == 'R')
				c = c.roll(4);
			else if(in[0] == 'L')
				c = c.roll(5);
			sum += c.d[0];
		}
		cout << sum << endl;
	}
	return 0;
}

Measured memory_bytes: 3108
// Template from https://techracho.bpsinc.jp/jhonda/2019_08_05/78537

// input macro for competive-programming from https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };

    ($iter:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, bytes) => {
        read_value!($iter, String).into_bytes()
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    use std::io::Read;
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();

    println!("{}", solve(&s));
}

macro_rules! test {
    ($($input:expr => $output:expr),* $(,)*) => {
        #[test]
        fn solve_test() {
            $(
                assert_eq!(solve($input), $output);
            )*
        }
    };
}

test! {
r#"3
2 1 4
2
1 1
2 3"# => r#"6
9"#,
}

fn solve(src: &str) -> String {
    input! {
        source = src,
        n: usize,
        t: [usize; n],
        m: usize,
        px: [(usize, usize); m],
    }
    let mut ans = "".to_string();

    for i in 0..m {
        let mut nt = t.clone();
        nt[ px[i].0 - 1 ] = px[i].1;
        ans.push_str(&nt.iter().sum::<usize>().to_string());
        if i != m - 1 {
            ans.push_str(&"\n");
        }
    }

    ans.to_string()
}

Measured memory_bytes: 4352
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cmath>
#include <list>
#include <numeric>
#include <stack>
#include <iomanip>
#include <complex>
#include <functional>
#include <tuple>

#define Rep(i,a,b) for(ll i = a; i < b; ++i)
#define rep(i,b) Rep(i,0,b)
#define allof(a) (a).begin(), (a).end()

#define Yes(q) ((q) ? "Yes" : "No")
#define YES(q) ((q) ? "YES" : "NO")
#define Possible(q) ((q) ? "Possible" : "Impossible")
#define POSSIBLE(q) ((q) ? "POSSIBLE" : "IMPOSSIBLE")

using namespace std;

using ll = long long;

constexpr int inf = 1e9 + 7;
constexpr ll infll = 1ll << 60ll;
constexpr ll mod = 1e9 + 7;
// 0~3までは右左下上 4~7までは斜め
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

namespace {
    template<typename T> void chmax(T& a, T b) { a = std::max(a, b); }
    template<typename T> void chmin(T& a, T b) { a = std::min(a, b); }

    void Cout(long long x, const char* end = "\n") { std::cout << x << end; }
    template <typename T> void Cout(const T& x, const char* end = "\n") { std::cout << x << end; }
    template <typename T> void Cout(const std::vector<T>& x, const char* sep = " ", const char* end = "\n") { for (std::size_t i = 0, sz = x.size(); i < sz; i++) { std::cout << x[i] << (i == sz - 1 ? end : sep); } }

    // 標準入出力
    struct inp {
        std::size_t sz;
        inp(std::size_t _sz = 1) : sz(_sz) {}
        template <typename T> operator T () const { T a; std::cin >> a; return a; }
        template <typename T> operator std::vector<T>() const { std::vector<T> a(sz); for (std::size_t i = 0; i < sz; i++) std::cin >> a[i]; return a; }
    };

    // 2次元用の標準入出力
    template<typename T>
    struct inpn {
        std::size_t szi, szj;
        inpn(std::size_t _szi, std::size_t _szj) : szi(_szi), szj(_szj) {}
        operator std::vector<std::vector<T>>() const {
            std::vector<std::vector<T>> a(szi, std::vector<T>(szj));
            for (std::size_t i = 0; i < szi; ++i)
                for (std::size_t j = 0; j < szj; ++j) cin >> a[i][j];
            return a;
        }
    };

    inp inp1; // input one
}


int main() {

    int n = inp1;
    string s = inp1;

    vector<vector<int>> sum(3, vector<int>(n + 1));

    const string pat = "RGB";
    rep(i, n) {
        int c = pat.find(s[i]);
        ++sum[c][i + 1];
    }

    rep(i, n) rep(j, 3) sum[j][i + 1] += sum[j][i];

    ll ans = 0LL;

    rep(i, n) {
        Rep(j, i + 1, n) {
            if (s[i] == s[j]) continue;
            int dif = j - i;

            // 残りの色はこれ以降いくつあるか
            int c = pat.find(s[i] ^ s[j] ^ 'R' ^ 'G' ^ 'B'); // 排他的論理和で求めてる　天才か
            int add = sum[c][n] - sum[c][j];

            // j - i != k - jの制約ある
            if (j + dif < n && s[j + dif] == pat[c]) --add;

            ans += add;
        }
    }

    Cout(ans);

    // 強い人のコードは強い

    return 0;
}

Measured memory_bytes: 3624
//g++ -std=c++14 test.cpp -o test.out
//問題URL:
//https://atcoder.jp/contests/abc164/tasks/abc164_e

//参考：
//https://drken1215.hatenablog.com/entry/2020/04/27/190000

//ポイント：
//グラフそのものにレイヤーをイメージするという考え方

//ダイクストラの計算量見積もりは
//グラフの頂点数と辺の数に注目すれば良い

//レイヤー化されたグラフの
//総頂点数は、最大でも元のグラフの頂点数50と状態数2500より
//50*2500 = 125000

//さらに辺の数は
//金貨を1枚両替（上へ行く）するという選択肢が各頂点について取れるのでこれが50
//元のグラフの辺の数がM=100
//1層分についてこれらが合計(50+100)=(N+M)
//これが最大で2500層あるので(50+100)*2500 = 375000

//よって全体ではElogV = 375000*log125000くらいになり間に合う

//レイヤー化されたグラフで頂点数や辺の数を求めるときは、
//まず1層分の総数に注目して、それから層の数分かけてやれば良い

#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <stack>
#include <map> 
#include <unordered_map> 
#include <utility>
#include <limits.h>
#include <bitset>
#include <set>
using namespace std;
 
#define LL long long int
const LL INF = (1LL<<60);
const int INF_INT = 2147483647-1e6-1;
const LL mod = 1000000007ll;
const int mod_int = 1000000007;

LL N,M,S;
vector<vector<tuple<LL,LL,LL>>> adj;
LL C[51],D[51];

LL ans[51];

void solve(){
	S = min(2500LL,S);
	//レイヤー分けされたグラフを考えダイクストラ 
	//tuple<点iに残り銀貨j枚で到達するための最短距離,i,j>
	priority_queue<tuple<LL,LL,LL>,vector<tuple<LL,LL,LL>>,greater<tuple<LL,LL,LL>>> q;
	q.push(tuple<LL,LL,LL>(0,1,S));
	//わかっている中での、点iに残り銀貨j枚で到達するための最短距離をdist[i][j]とする
	vector<vector<LL>> dist(N+1,vector<LL>(2501,INF));
	dist[1][S] = 0;
	while(!q.empty()){
		LL dist_ij = get<0>(q.top());//点iに残り銀貨j枚で到達するための最短距離
		LL i = get<1>(q.top());//点i
		LL j = get<2>(q.top());//残り銀貨j枚
		q.pop();
		if(dist[i][j]<dist_ij) continue;
		//銀貨を補充
		if(j+C[i]<=2500){
			LL next_j = j + C[i];
			if(dist[i][next_j]>dist[i][j]+D[i]){
				dist[i][next_j] = dist[i][j]+D[i];
				q.push(tuple<LL,LL,LL>(dist[i][next_j],i,next_j));
			}
		}
		//列車に乗る
		for(auto next:adj[i]){
			LL next_i = get<0>(next);
			LL silver_required = get<1>(next);
			LL time_required = get<2>(next);

			LL next_j = j-silver_required;
			if(next_j<0) continue;

			if(dist[next_i][next_j]>dist[i][j]+time_required){
				dist[next_i][next_j] = dist[i][j]+time_required;
				q.push(tuple<LL,LL,LL>(dist[next_i][next_j],next_i,next_j));
			}
		}
	}

	for(int i=2;i<=N;i++){
		ans[i] = INF;
		for(int j=0;j<=2500;j++){
			ans[i] = min(ans[i],dist[i][j]);
		}
	}
}

int main(){
    cin >> N >> M >> S;
    adj = vector<vector<tuple<LL,LL,LL>>>(N+1);
    for(int i=0;i<M;i++){
    	LL u,v,a,b;cin >> u >> v >> a >> b;
    	adj[u].push_back(tuple<LL,LL,LL>(v,a,b));
    	adj[v].push_back(tuple<LL,LL,LL>(u,a,b));
    }
    for(int i=1;i<=N;i++) cin >> C[i] >> D[i];

    solve();

    for(int i=2;i<=N;i++) cout << ans[i] << endl;
    return 0;
}

Measured memory_bytes: 6972
s = str(input())
l = -1
r = -1
for i in range(len(s)):
    if (s[i]=='A')&(l==-1):
        l=i
    if (s[len(s)-1-i]=='Z')&(r==-1):
        r=len(s)-1-i
    if (r>=0)&(l>=0):
        break
print(r-l+1)

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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit(b) (1ll << (b))
#define uniq(v) (v).erase(unique(all(v)), (v).end())
#define rsort(v) sort(all(v)); reverse(all(v))

using namespace std;

using i32 = int;
using i64 = long long;
using f80 = long double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << '\n'; exit(0); }
inline void no() { cout << "No" << '\n'; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { return a / gcd(a, b) * b; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }
template<typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template<typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template<typename T> inline void amax(T &x, T y) { if (x >= y) x = y; }
template<typename T> inline void amin(T &x, T y) { if (x <= y) x = y; }
template<typename T> inline T power(T x, i64 n) { T r = 1; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template<typename T> istream& operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; }
template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }

void solve() {
  int x, y; cin >> x >> y;
  if (x % y == 0) cout << -1 << '\n';
  else cout << x << '\n';
}


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

//#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

#define LL long long

int inp[200005];

int main() {
	LL n,k;

	cin >> n >> k;
	for(int i=1;i<=n;i++)
		cin >> inp[i];

	if(inp[1] == 1) {
		cout << 1 << endl;
		return 0;
	}

	vector<int> path;
	set<int> st;
	int cycPt;

	path.push_back(1);
	st.insert(1);

	int curr = inp[1];
	
	while(1) {
		if(st.find(curr) != st.end()) {
			cycPt = curr;	
			break;
		}
		path.push_back(curr);
		st.insert(curr);
		curr = inp[curr];
	}

	vector<int> non, cyc;
	int flag = 0;
	for(int i=0;i<path.size();i++) {
		if(flag == 1)
			cyc.push_back(path[i]);
		else
			non.push_back(path[i]);
		if(path[i] == cycPt) {
			cyc.push_back(path[i]);
			flag = 1;
		} 
	}

	int len = non.size();
	int cyclen = cyc.size();

	if(k <= len - 1) {
		cout << non[k] << endl;
	} else {
		k = k - (len-1);
		k = k % cyclen;
		cout << cyc[k] << endl;
	}

	return 0;
}


Measured memory_bytes: 15488
n = int(input())
nums = list(map(int, input().split()))
count = 0
for i in range(n):
    mini = i
    for j in range(i, n):
        if nums[j] < nums[mini]:
            mini = j
    if mini != i:
        count += 1
        nums[i], nums[mini] = nums[mini], nums[i]
for i in range(n-1):
    print(nums[i], end = ' ')
print(nums[n-1])
print(count)        


Measured memory_bytes: 5612
#include <cstdio>
#include <cstring>

using namespace std;

int bak[26];
void toMin(char *s){
  for (char *p=s; *p; *p++){
    bak[*p-'a']++;
  }
  for (int i=0; i<26; i++){
    while(bak[i]){
      bak[i]--;
      *s++ = i+'a';
    }
  }
}
void toMax(char *s){
  for (char *p=s; *p; *p++){
    bak[*p-'a']++;
  }
  for (int i=25; i>=0; i--){
    while(bak[i]){
      bak[i]--;
      *s++ = i+'a';
    }
  }
}

int main(void){
  char s[128], t[128];
  
  scanf("%s", s);
  scanf("%s", t);
  toMin(s);
  toMax(t);
//  puts(s);
//  puts(t);
  puts(strcmp(s,t)<0?"Yes":"No");
  
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
long long ans=753,sum;
char j;
int main(){
    while(cin>>j){
        if(j>='0'&&j<='9'){
            sum=sum*10+j-'0';
            sum%=1000;
            ans=min(ans,abs(sum-753));
        }
    }cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#末端の処理を変更
s_ = "x"+input()+"x"
s = []
c = []
cnt = 0
"""
if s_[0]!="x":
    c.append(0)
"""
for i in range(len(s_)):
    if s_[i]!="x":
        c.append(cnt)
        cnt = 0
        s.append(s_[i])
    else:
        cnt += 1
c.append(cnt)

l = len(s)
for i in range(l//2):
    if s[i]!=s[l-i-1]:
        print(-1)
        exit()
ans = 0
l2 = len(c)
for i in range(l2):
    ans += abs(c[i]-c[l2-i-1])

print(ans//2)


Measured memory_bytes: 54768
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#define swap(type,a,b) do{type t=a;a=b;b=t;}while(0);
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define ll long long
#define INF 100000000
#define FOR(i,a,n) for(i=(a);i<(n);i++)
int comp(const void* a,const void* b){
	return *(int*)a-*(int*)b;
}
void fill(int a[],int b,int c){
	int i;
	FOR(i,0,b) a[i]=c;
	return;
}
int main(void)
{
	int i;
	ll k,a,b;
	scanf("%lld",&k);
	a=k/50,b=k%50;
	puts("50");
	FOR(i,0,50){
		if(i<b) printf("%lld",i+a-b+51);
		else printf("%lld",i+a-b);
		printf("%c",i==49?'\n':' ');
	}
	return 0;
}

Measured memory_bytes: 128
import sys
n = int(input())
xyh = [list(map(int, input().split())) for i in range(n)]
cnt = 0
for i in range(n):
  if xyh[i][2] != 0:
    cnt += 1
if cnt == 1:
  for i in range(n):
    if xyh[i][2] != 0:
      print(" ".join(list(map(str, xyh[i]))))
      sys.exit()
for i in range(101):
  for j in range(101):
    x = []
    for k in range(n):
      if xyh[k][2] != 0:
        x.append(abs(xyh[k][0]-i)+abs(xyh[k][1]-j)+xyh[k][2])
    if len(set(x)) == 1:
      print(i, j, x[0])

Measured memory_bytes: 9104
#include<stdio.h>
#include<string.h>

int main(int argc, char *argv[]){

     char find[11];
     char in[1001];
     char *word;
     int cnt = 0;

     scanf("%s", find);
     while (1) {

        scanf("%s", in);
        for (word = strtok(in, " "); word; word = strtok(NULL, " ")) {

            if (!strcmp(word, "END_OF_TEXT")) goto END;
            if (!strcasecmp(word, find)) cnt++;

         }

     }
END:
        printf("%d\n", cnt);
        return 0;
}

Measured memory_bytes: 556
N = int(input())
M = list(map(int, input().split()))
M = [bin(m)[2:] for m in M]
max_len = max([len(m) for m in M])
M = ["0"*(max_len-len(m))+m for m in M]
MOD = 10**9+7
result = 0
for i in range(1, max_len+1):
  zero = len([m[-i] for m in M if m[-i]=="0"])
  one = len(M) - zero
  #print(one, zero, i)
  result += (((one * zero) % MOD) * ((2 ** (i-1)) % MOD) % MOD)
  result %= MOD
print(result)

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

using namespace std;
#define int long long
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

signed main(){
    int A[3];
    cin >> A[0] >> A[1] >> A[2];
    
    sort(A,A+3);
    
    if(A[0] == 5 && A[1] == 5 && A[2] == 7){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
    return 0;
}


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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define all(x) (x).begin(),(x).end()
#define foreach(u,v) for(auto (u) : (v))
#define pb push_back
#define mp make_pair
#define mt make_tuple

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;

const int inf = 1e9;
const ll linf = 1LL<<60;
const ll mod = 1e9 + 7;
const double eps = 1e-9;

/*
*/

int main()
{
  int k;
  cin >> k;
  cout << k/2 * (k/2+k%2) << endl;

  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define ll long long
#define INF 1000000000000000000

double dist(double x1, double x2, double y1, double y2) {
    double res = sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
    return res;
}

int main() {
    int N;
    cin >> N;
    vector<double> A, X, Y;
    rep(i, N) {
        A.push_back(i);

        double x, y;
        cin >> x >> y;
        X.push_back(x);
        Y.push_back(y);
    }

    double sum = 0, cnt = 0;
    do {
        double x1, x2, y1, y2;
        rep(i, N - 1) {
            x1 = X[A[i]], x2 = X[A[i + 1]];
            y1 = Y[A[i]], y2 = Y[A[i + 1]];
            sum += dist(x1, x2, y1, y2);
        }
        cnt++;
    } while (next_permutation(all(A)));

    double res = sum / cnt;
    cout << fixed << setprecision(10) << res << endl;
}

Measured memory_bytes: 256
dd = int(input())
c = list(list(map(int, input().split())))
s = [[0]*26]*dd
v = [[0]*26]*dd
vs = [[0]*26]*dd
ans = [0]*dd
fdate = [0]*26
for i in range(dd):
    s[i] = list(list(map(int, input().split())))



for i in range(dd):

    for j in range(26):
        v[i][j] = s[i][j] + c[j] *(i-fdate[j])
    maxv = -100000
    for j in range(26):
        if maxv < v[i][j]:
            maxv = v[i][j]
            ans[i]=j+1
    fdate[ans[i]-1] =i+1

for a in ans:
    print(a)

Measured memory_bytes: 73744
#include<stdio.h>

int main(){
        int n, m, i, count=0;
        scanf("%d %d", &n, &m);
        int h[n], a[m], b[m], counter[n];
        for(i=0; i<n; i++){
                scanf("%d", &h[i]);
                counter[i]=0;
        }
        for(i=0; i<m; i++){
                scanf("%d %d", &a[i], &b[i]);
                if(h[a[i]-1]==h[b[i]-1]){
                        counter[a[i]-1]=1;
                        counter[b[i]-1]=1;
                }else if(h[a[i]-1]>h[b[i]-1]){
                        counter[b[i]-1]=1;
                }else{
                        counter[a[i]-1]=1;
                }
        }

        for(i=0; i<n; i++){
                if(counter[i]==0){
                        count++;
                }
        }
        printf("%d", count);

        return 0;
}


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

typedef long long ll;
//const int INF = 2e9;
//const ll INF = 9e18;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    map<int,int> d;
    for (int i=0;i<N;i++){
        int a;
        cin >> a;
        if (d.find(a) == d.end()) d[a] = 1;
        else d[a]++;
    }
    bool ans = true;
    if (d.size() > 3) {
        ans = false;
    } else if (d.size() == 3) {
        int val = 0;
        bool flag = true;
        for (auto it = d.begin();it!=d.end();it++){
            val ^= it->first;
            if (it->second != N/3) flag = false; 
        }
        if (val || !flag || N%3) ans = false;
    } else if (d.size() == 2) {
        bool flag = false;
        int numzero;
        int numelse;
        for (auto it = d.begin();it!=d.end();it++){
            if (it->first == 0) {
                flag = true;
                numzero = it->second;
            } else {
                numelse = it->second;
            }
        }
        if (!flag || numzero != N/3 || numelse != N*2/3) {
            ans = false;
        }
    } else if (d.size() == 1) {
        if (d.find(0) == d.end()) ans = false;
    }
    if (ans) cout << "Yes" << "\n";
    else cout << "No" << "\n";
}

Measured memory_bytes: 3840
use proconio::input;

fn main() {
    input! {
        n: usize,
        d: [(usize, usize); n],
    }

    let mut q = 0;
    for (a, b) in d {
        if a == b {
            q += 1;
        } else {
            q = 0;
        }
        if q == 3 {
            println!("Yes");
            return;
        }
    }
    println!("No");
}


Measured memory_bytes: 2160
#include <iostream>
#include <algorithm>

using namespace std;

long long int H, W, c[10][10] = {}, A, dist[10][10] = {}, ans = 0;
long long int inf = 100000000;
bool visited[10] = {};

int main() {
	cin >> H >> W;
	for (int i = 0; i <= 9; i++) {
		for (int j = 0; j <= 9; j++)cin >> c[i][j];
	}
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			cin >> A;
			if (A == 1 || A == -1)continue;
			for (int k = 0; k <= 9; k++) {
				for (int l = 0; l <= 9; l++)dist[k][l] = inf;
				visited[k] = false;
			}
			if (dist[A][1] != inf) {
				ans += dist[A][1];
				continue;
			}
			int cur = A;
			dist[A][A] = 0;
			while (cur != 1) {
				visited[cur] = true;
				for (int k = 0; k <= 9; k++) {
					if (c[cur][k] != 0)dist[A][k] = min(dist[A][k], dist[A][cur] + c[cur][k]);
				}
				for (int k = 0; k <= 9; k++) {
					if (!visited[k]) {
						cur = k;
						break;
					}
				}
				for (int k = 0; k <= 9; k++) {
					if (!visited[k] && dist[A][cur] > dist[A][k] && dist[A][k] != 0)cur = k;
				}
			}
			ans += dist[A][1];
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>

#define rep(i,N) for(int (i)=0;(i)<(N);(i)++)

using namespace std;

int main(){
	string s;
	int K,count = 0;
	cin >> s;
	cin >> K;
	rep(i, 100) {
		if (s[i] == '1')count++;
		else break;
	}
	if (count == 0) {
		cout << s[0];
	}
	else if (count < K) {
		cout << s[count];
	}
	else {
		cout << '1';
	}
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
int n,k,pos=-1,ans=0x7f7f7f7f,a[100010];
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",a+i);
		if(pos==-1&&a[i]>0)
			pos=i-1;
	}
	if(pos==-1)
		pos=n;
	if(pos+k<=n)
		ans=a[pos+k];
	if(pos-k+1>0)
		ans=min(ans,-a[pos-k+1]);
	for(int j=pos;j>0&&pos-j+1<k;j--)
		if(j+k-1<=n)
			ans=min(ans,a[j+k-1]-a[j]+min(abs(a[j+k-1]),abs(a[j])));
	printf("%d",ans);
	return 0;
}

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

int main() {
  int A, B;
  cin >> A >> B;

  int ans = 0;

  for (int i = A; i <= B; i++) {
   if (i % 100 == i % 10000 / 1000 * 10 + i / 10000) ans++;
  }

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

Measured memory_bytes: 256
#include <stdio.h>
int main(){
    int n,now=1,a[10000],ans;
    bool prime[60000],f;
    a[0]=2;
    for(int i=3;i<60000;i+=2){
        prime[i]=true;
    }
    for(int i=3;i<=60000;i+=2){
        if(prime[i]){
            a[now]=i;
            now++;
            if((long long)i*i<60000){
            for(int j=i*i;j<60000;j+=i){
                prime[j]=false;
            }
            }
        }
    }
    while(1){
        scanf("%d",&n);
        if(n==0)return 0;
        ans=now=0;
        if(n%2==1){
            f=true;
            n-=2;
            for(int i=0;a[i]<=n&&f;i++){
                if(a[i]==n){printf("1\n");
                    f=false;
                }
            }
            if(f)printf("0\n");
        }
        else {
            while(a[now]<=n)now++;
            now--;
            for(int i=0;i<=now;i++){
                while(a[i]+a[now]>n)now--;
                if(i>now)continue;
                for(int j=i;a[j]+a[now]<=n&&j<=now;j++){
                    if(a[j]+a[now]==n){
                        ans++;
                        now--;
                        break;
                    }
                }
            }
            printf("%d\n",ans);
        }
    }
}

Measured memory_bytes: 2680
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>

using namespace std;

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

#define reps(i,f,n) for(int i = int(f); i <= int(n); i++)
#define rep(i,n) reps(i,0,int(n)-1)
#define rrep(i,n) for(int i = n-1; i >= 0; i--)

#define all(x) (x).begin(),(x).end()
#define X first
#define Y second

#define sz size()
#define eb emplace_back

int c[128][128];

int main(void){
  int n;
  while(cin >> n, n){
    int W,H,w,h;
    int x,y;
    int ans = 0;
    cin >> W >> H;
    rep(i,128)rep(j,128)c[i][j] = 0;

    rep(i,n){
      cin >> x >> y;
      c[y][x] = 1;
    }

    cin >> w >> h;

    rep(i,127) rep(j,127) c[i+1][j] += c[i][j];
    rep(i,127) rep(j,127) c[i][j+1] += c[i][j];

   // cout << "(" <<  w << "," << h << ")" << endl;

    rep(i,127) rep(j,127){
      if(i+h<=H && j+w<=W){
        ans=max(ans,c[i+h][j+w]+c[i][j]-c[i+h][j]-c[i][j+w]);
      }
    }
    cout << ans << endl;

  }

  return 0;
}

Measured memory_bytes: 3160
#include<bits/stdc++.h>
#define maxn 1000006
using namespace std;

int n,q[maxn],ql=1,qr;
char s[maxn],t[maxn];

int main(){
	scanf("%d",&n);
	scanf("%s%s",s+1,t+1);
	if(strcmp(s+1,t+1)==0){
		puts("0");
		return 0;
	}
	int pos=n,ans=0;
	for(int i=n;i>=1;i--){
		if(t[i] == t[i-1]) continue;
		pos = min(pos , i);
		for(;pos && t[i] != s[pos];pos--);
		if(!pos){ puts("-1");return 0; }
		for(;ql<=qr && q[ql] - (qr-ql) > i;ql++);
		q[++qr] = pos;
		if(i^pos) ans = max(ans , qr-ql+1);
	}
	printf("%d\n",ans+1);
}

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

# define Rep(i,a,b) for(int i=a;i<=b;i++)
# define _Rep(i,a,b) for(int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)

typedef long long ll;

const int N=1e5+5;

template<typename T> void read(T &x){
   x=0;int f=1;
   char c=getchar();
   for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
   for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
    x*=f;
}

int x;

int main()
{
    read(x);
    if(x<=599)puts("8");
    else if(x<=799)puts("7");
    else if(x<=999)puts("6");
    else if(x<=1199)puts("5");
    else if(x<=1399)puts("4");
    else if(x<=1599)puts("3");
    else if(x<=1799)puts("2");
    else puts("1");
    return 0;
}

Measured memory_bytes: 3616
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
#include <sstream>
#include <set>
using namespace std;
using ll = long long;

class range {private: struct I{int x;int operator*(){return x;}bool operator!=(I& lhs){return x<lhs.x;}void operator++(){++x;}};I i,n;
public:range(int n):i({0}),n({n}){}range(int i,int n):i({i}),n({n}){}I& begin(){return i;}I& end(){return n;}};

int main() {
  string s;
  while (cin >> s) {
    bool v[256];
    memset(v, 0, sizeof(v));
    for (char c : s) {
      v[(int)c] = 1;
    }

    if (v['N'] == v['S'] && v['W'] == v['E']) {
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
  }
}


Measured memory_bytes: 764
N, Y = map(int, input().split())

for x in range(N+1):
    for y in range(N-x+1):
        z = N - x - y
        if 10000*x + 5000*y + 1000*z == Y:
            print(x, y, z)
            exit()
            
            
print(-1, -1, -1)





Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,k;
  cin>>n>>k;
  int a[n];
  for(int i=0;i<n;i++)
    cin>>a[i];
  int dp[n];
  dp[0]=0;
  for(int i=1;i<n;i++)
  {
    int count=INT_MAX;
    for(int j=(i-1);((j>=0)&((i-j)<=k));j--)
    {
      count=min(count,dp[j]+abs(a[i]-a[j]));
    }
    dp[i]=count;
  }
    cout<<dp[n-1]<<endl;
}

Measured memory_bytes: 4376
a, b, c, d = map(int, input().split())


# a-c
ac_len = max(a,c) - min(a,c)
if ac_len <= d:
    print("Yes")
    exit()

# a-b-c

ab_len = max(a,b) - min(a,b)
bc_len = max(b,c) - min(b,c)
if ab_len <= d and bc_len <= d:
    print("Yes")
    exit()
print("No")


Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define endl '\n'
#define ll long long
using namespace std;

const int MXN = 1e5 + 5;
int n;
int h[MXN];
int dp[MXN];

int Dp(int idx) {
    if(idx == n - 1) return 0; // caso base
    if(dp[idx] != -1) return dp[idx]; // caso dp
    int ans = Dp(idx + 1) + abs(h[idx] - h[idx + 1]);
    if(idx + 2 < n) ans = min(ans, Dp(idx + 2) + abs(h[idx] - h[idx + 2])); 
    return dp[idx] = ans; // guardar
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> h[i];
    }
    // memset(dp, -1, sizeof dp);
    // cout << Dp(0) << endl;
    for(int i = n - 2; i >= 0; i--) {
        dp[i] = dp[i + 1] + abs(h[i] - h[i + 1]);
        if(i + 2 < n) dp[i] = min(dp[i], dp[i + 2] + abs(h[i] - h[i + 2]));
    }
    cout << dp[0] << endl;
    return 0;
}

Measured memory_bytes: 4392
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

const int maxn = 1005;

int n;
vector<int> G[maxn];
int x[maxn];
int dp[maxn][5 * maxn];
int f[maxn];

void dfs(int v){
    int m = G[v].size();
    for(auto u : G[v]){
        dfs(u);
    }
    for(int i = 0;i <= x[v];i++){
        for(int j = 0;j <= m;j++){
            dp[j][i] = 1e9;
        }
    }
    dp[0][0] = 0;
    for(int i = 1;i <= m;i++){
        int u = G[v][i - 1];
        for(int j = 0;j <= x[v];j++){
            if(j >= x[u]){
                dp[i][j] = min(dp[i][j], dp[i - 1][j - x[u]] + f[u]);
            }
            if(j >= f[u]){
                dp[i][j] = min(dp[i][j], dp[i - 1][j - f[u]] + x[u]);
            }
        }
    }
    f[v] = 1e9;
    for(int j = 0;j <= x[v];j++){
        f[v] = min(f[v], dp[m][j]);
    }
}

int main(){
    cin >> n;
    for(int i = 2;i <= n;i++){
        int p;
        scanf("%d", &p);
        G[p].push_back(i); 
    }
    for(int i = 1;i <= n;i++){
        scanf("%d", &x[i]);
    }
    dfs(1);
    if(f[1] == 1e9){
        cout << "IMPOSSIBLE" << endl;
    }else{
        cout << "POSSIBLE" << endl;
    }
    return 0;
}


Measured memory_bytes: 17280
#include<iostream>
using namespace std;
using  ll = long long;
int main(){
  ll a, b, A=0, B=0;
  cin >> a >> b;
  for(int i = 0; i < a; i++){
    A *= 10;
    A += b;
  }
  for(int i = 0; i < b; i++){
    B *= 10;
    B += a;
  }
  cout << ( (a>b)?(A):(B) );
  return 0;
}

Measured memory_bytes: 256
from fractions import gcd
n,m=map(int,input().split())
s=input()
t=input()
g=gcd(n,m)
a=n//g
b=m//g
for i in range(g):
  if s[a*i]!=t[b*i]:
    print(-1)
    break
else:
  print(n*m//g)

Measured memory_bytes: 5432
#include <bits/stdc++.h>
#define rep(i, a, b) for(ll i = ll(a); i < ll(b); i++)
#define rer(i, a, b) for(ll i = ll(a) - 1; i >= ll(b); i--)
#define sz(v) (int)(v).size()
#define pb push_back
#define sc second
#define fr first
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
using namespace std;
typedef long long int ll;
typedef pair <ll, pair<pair<ll,ll>, ll>> P;

const ll MOD=1000000007;
int N,X;
ll b[100000], l[100000], u[100000];
P S[100000];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>N>>X;
    rep(i,0,N) cin>>b[i]>>l[i]>>u[i];
    ll res=0;
    rep(i,0,N){
        S[i].fr=(X-b[i])*u[i]+b[i]*l[i];
        S[i].sc.sc=b[i];
        S[i].sc.fr.fr=u[i];
        S[i].sc.fr.sc=l[i];
        res+=-b[i]*l[i];
    }
    sort(S, S+N);
    ll ng=0, ok=N;
    while(ok-ng>1){
        ll mid=(ok+ng)/2;
        ll temp=res;
        rer(i,N,N-mid){
            temp+=S[i].fr;
        }
        if(temp>=0) ok=mid;
        else ng=mid;
    }
    rer(i,N,N-ok+1){
        res+=S[i].fr;
    }
    ll ans=X*ok;
    rep(i,0,N-ok+1){
        if(res+S[i].fr>=0){
            if(res+S[i].sc.sc*S[i].sc.fr.sc<0){
                ans=min(ans, X*ok-(res+S[i].fr)/S[i].sc.fr.fr);
            }
            else{
                ans=min(ans, X*(ok-1)+S[i].sc.sc-(res+S[i].sc.sc*S[i].sc.fr.sc)/S[i].sc.fr.sc);
            }
        }
    }
    res+=S[N-ok].fr;
    rep(i,N-ok+1,N){
        ll temp=res-S[i].fr;
        if(temp+S[i].fr>=0){
            if(temp+S[i].sc.sc*S[i].sc.fr.sc<0){
                ans=min(ans, X*ok-(temp+S[i].fr)/S[i].sc.fr.fr);
            }
            else{
                ans=min(ans, X*(ok-1)+S[i].sc.sc-(temp+S[i].sc.sc*S[i].sc.fr.sc)/S[i].sc.fr.sc);
            }
        }
    }
    cout <<ans<<"\n";
}

Measured memory_bytes: 5760
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <map>
#include <stack>

#define rep(i, N) for (int i = 0; i < (int)N; i++)
using namespace std;
typedef long long ll;
const ll LLINF = 9223372036854775807;
const int INF = pow(2,29);
const int MOD = 1000000007;

struct UnionFind {
  vector<int> par;
  vector<int> size;

  UnionFind(int N) : par(N), size(N) { rep(i, N) { par[i] = i; size[i]=1; } }

  int root(int x) { 
    if (par[x]== x) return x;
    else return par[x] = root(par[x]);
  }

  void unite(int x, int y) {
    int rx = root(x);
    int ry = root(y);
    if (rx==ry) return;
    par[rx] = ry;
    size[ry] += size[rx];
    size[rx] = 0;
  }

  bool same(int x, int y) {
    return root(x) == root(y);
  }

  ll decay(int x, int y) {
    int rx = root(x);
    int ry = root(y);
    return size[rx] * size[ry];   
  }

};

int main() {
  int N, M; cin >> N >> M;
  int A[M], B[M]; 
  rep(i,M) { cin >> A[i] >> B[i]; A[i]--; B[i]--; }
 
  UnionFind tree(N);
  ll rt[M]; fill_n(rt,M,0);
  for (int i=M-1; i>=0; i--) {
    if (!tree.same(A[i], B[i])) {
      rt[i] = tree.decay(A[i], B[i]);
      tree.unite(A[i], B[i]);
    }
  }

  ll result = 0;
  rep(i,M) {
    result += rt[i];
    cout << result << endl;
  }
  return 0;
}

Measured memory_bytes: 3712
<?php
  list($n) = explode(" ", trim(fgets(STDIN)));
  $n=intval($n);

  $amin=PHP_INT_MAX;
  $amax=PHP_INT_MIN;
  $bmin=PHP_INT_MAX;
  $bmax=PHP_INT_MIN;
  for ($i=0; $i<$n; $i++) {
    list($x,$y) = explode(" ", trim(fgets(STDIN)));
    $amin=min($amin, $x+$y);
    $amax=max($amax, $x+$y);
    $bmin=min($bmin, $x-$y);
    $bmax=max($bmax, $x-$y);
  }

  echo max($bmax-$bmin, $amax-$amin);

Measured memory_bytes: 16308
#include <algorithm>
#include <cmath>
#include <iostream>
#include <limits>
#include <numeric>
#include <string>
#include <vector>

#define rep(i, x, n) for(int i = x; i < n; i++)
using namespace std;
const long long INF = 1LL << 60;

long long GCD(long long a, long long b) {
    if(b == 0)
        return a;
    else
        return GCD(b, a % b);
}
long long LCM(long long a, long long b) {
    long long g = GCD(a, b);
    return a / g * b;
}
int main() {
    int N;
    cin >> N;
    vector<long long> H(N);
    rep(i, 0, N) { cin >> H[i]; }
    int res = 0;
    long long tmp = H[0];
    int count = 0;
    rep(i, 1, N) {
        if(tmp >= H[i]) {
            count++;
            if(count > res) {
                res = count;
            }

        } else {
            count = 0;
        }
        tmp = H[i];
    }
    cout << res << endl;
}

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

#define rep(i, n) for(int (i) = 0; i < (n); ++(i))

typedef long long ll;
const ll MOD = 1e9 + 7;

int main() {
  int N;
  std::cin >> N;

  std::string P, Q;
  rep(i, N) {
    char c;
    std::cin >> c;
    P.push_back(c);
  }
  rep(i, N) {
    char c;
    std::cin >> c;
    Q.push_back(c);
  }

  std::string base;
  rep(i, N) {
    base.push_back('0' + i + 1);
  }

  int a, b;
  int cnt = 1;
  do {
    if(base == P) {
      a = cnt;
    }
    if(base == Q) {
      b = cnt;
    }
    ++a;
    ++b;
  } while(std::next_permutation(base.begin(), base.end()));

  std::cout << std::abs(a - b) << '\n';
}


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

using namespace std;

int N = 100005;
long long int A[100005];

set<long long int> S;

int main(void) {

	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
	}

	for (int i = 1; i <= N; i++) {
		if (S.count(A[i]) == 0) { S.insert(A[i]); }
		else { S.erase(A[i]); }
	}

	cout << S.size() << endl;
	//system("pause");
	return 0;
}

Measured memory_bytes: 5760
#include <cstdio>
#include <vector>
#include <algorithm>

int main() {
  size_t n;
  scanf("%zu", &n);

  std::vector<int> a(n);
  for (auto& ai: a) scanf("%d", &ai);

  std::sort(a.begin(), a.end());

  int ai = a.back();

  auto it = std::lower_bound(a.begin(), a.end()-1, ai/2);
  if (it > a.begin() && it[0]-ai/2 > ai/2-it[-1]) --it;
  if (it == a.end()-1) --it;
  int aj = *it;

  printf("%d %d\n", ai, aj);
}


Measured memory_bytes: 1272
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
#define int long long
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define print0(a) cout << (a) << ' '
#define print1(a) cout << (a) << '\n'
#define print2(a,b) cout << (a) << ' ',print1(b)
#define print3(a,b,c) cout << (a) << ' ',print2(b,c)
#define print4(a,b,c,d) cout << (a) << ' ',print3(b,c,d)
#ifdef i_am_noob
#define debug(a) print2(#a,a)
#else
#define debug(a) 
#endif
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
 
using namespace std;
using namespace __gnu_pbds;
 
const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod2;
 
inline int add(int a, int b){return (a+b>=MOD?a+b-MOD:a+b);}
inline int sub(int a, int b){return (a+MOD-b>=MOD?a-b:a+MOD-b);}
int Pow(int a, int b){
	if(!b) return 1;
	int tmp=Pow(a*a%MOD,b>>1);
	return (b&1?tmp*a%MOD:tmp);
}
inline int inverse(int n){return Pow(n,MOD-2);}

const int maxn=200005;
//i_am_noob
int n,a[100];
ld k=0;

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	cout << fixed << setprecision(12);
	cin >> n;
	rep(n) cin >> a[i];
	rep(n) k+=1.0/a[i];
	print1(1/k);
	return 0;
}

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

aji = list(map(lambda x: L + x - 1, range(1, N + 1)))

if (aji[0] <= 0 and aji[N - 1] >= 0) :
    print(sum(aji))
elif (aji[0] < 0 and aji[N - 1] < 0):
    print(sum(aji) - aji[N -1])
else:
    print(sum(aji) - aji[0])

Measured memory_bytes: 3064
#include<iostream>
using namespace std;
int main()
{
	int n,a;
	while( cin >> n ){
		if(n == 0)
			break;
		a = 0;
		while( n != 0){
			a += n/5;
			n /= 5;
		}
		cout << a << endl;
	}
}

Measured memory_bytes: 0