akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[100001];
int dist[100001];
int depth[100001];
int parent[100001];
void dfs(int r,int p)
{
    parent[r]=p;
    for(auto x : adj[r])
    {
        if(x!=p)
        {
            dist[x] = dist[r]+1;
            dfs(x,r);
            depth[r] = max(depth[r],depth[x]+1);
        }
    }
}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
    int n;
    cin>>n;
    int s,d;
    cin>>d>>s;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(s,0);
    int t;
    int ans=0;
    t = dist[d];
    if(t&1)
    {
        ans = t/2;
        t = t/2;
        while(t>0)
        {
            d = parent[d];
            t--;
        }
        ans += depth[d];
    }
    else
    {
        t = t-2;
        t = t/2;
        ans = t;
        while(t>0)
        {
            d = parent[d];
            t--;
        }
        ans += depth[d]+1;
    }
    cout<<ans<<"\n";
    return 0;
}


Measured memory_bytes: 12032
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    string str;
    cin>>str;
    if(str.size()<=n)
    cout<<str;
    else
    {
        str=str.substr(0,n);
        str+="...";
        cout<<str;
        
    }
    
    
}

Measured memory_bytes: 3632
//
// Created by Wangzhe on 2019/10/19.
//

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll maxn = 300 + 10, INF = 0x3f3f3f3f;

int d1[maxn][maxn];

int mp[maxn][maxn];

int main() {
    int n,m,l; cin >> n >> m >>l;
//    for (int i = 0; i < n; i++) {
//        for (int j = 0; j < n; j++) {
//            mp[i][j] = i == j ? 0 : INF;
//            d1[i][j] = i == j ? 0 : INF;
//        }
//    }
    memset(mp, INF, sizeof mp);
    memset(d1, INF, sizeof d1);
    for (int i = 0; i < m; i++) {
        int x, y, z; cin >> x >> y >> z;
        x--; y--;
        mp[x][y] = mp[y][x] = min(mp[x][y],z);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                mp[j][k] = min(mp[j][k], mp[j][i] + mp[i][k]);
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++){
            if (mp[i][j] <= l) {
                d1[i][j] = 1;
            }
        }
        d1[i][i] = 0;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                d1[j][k] = min(d1[j][k], d1[j][i] + d1[i][k]);
            }
        }
    }

    int q; cin >> q;
    while (q--) {
        int s, t; cin >> s >>t;
        s--; t--;
        cout << ((d1[s][t] > 500) ? -1 : (d1[s][t] - 1)) << endl;
    }

    return 0;
}

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

int main(){
  string s; cin >> s;
  string s1 = s.substr(0, 2), s2 = s.substr(2);
  int a = stoi(s1), b = stoi(s2);
  if (a == 0 || a > 12){
    if (0 < b && b <= 12) cout << "YYMM";
    else cout << "NA";
  }else if (b == 0 || b > 12){
    cout << "MMYY";
  }else cout << "AMBIGUOUS";
  cout << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	private static Scanner sc=new Scanner(System.in);
	private static int n=sc.nextInt();
	private static final int N_MAX=1000;
	private static int[] a=new int[N_MAX+1];
	public static void main(String[] args){
		for(int i=2;i<=n;i++){
			int num=i;
			int j=2;
			while(num>1){
				if(num%j==0){
					a[j]++;
					num=num/j;
				}
				else j++;
			}
		}
		long ans=1;
		for(int j=2;j<=N_MAX;j++){
			ans=(ans*(a[j]+1))%1000000007;
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 23892
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,n) for(ll i = s; i < n; i++)
typedef long long ll;
const ll maxn = 100005;
const ll INF = 1e16;
ll N, W;
ll d[105][maxn];
ll w[maxn];
ll v[maxn];
ll dp(ll a, ll b){
	if(b<=0)return 0;
	if(d[a][b]!=-1)return d[a][b];
	ll ans = INF;
	ans = min(ans, dp(a-1, b-v[a])+w[a]);
	ans = min(ans, dp(a-1, b));
	return d[a][b] = ans;
}


int main(){
	cin>>N>>W;
	rep(i,1,N+1)cin>>w[i]>>v[i];
	memset(d,-1,sizeof d);
	rep(i,0,maxn) d[0][i] = INF;
	int sum = 0;
	rep(i,1,N+1)sum+=v[i];
	int left = 0; int right = sum+5;
	while(left<right){
		int mid = left +(right-left+1)/2;
		if(dp(N, mid)<=W)left = mid;
		else right = mid-1;
	}
	cout<<left<<endl;
}

Measured memory_bytes: 82304
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <cstring>
#include <stdio.h>
#include <iomanip>

using namespace std;

typedef long long int lli;
lli A[200005] = {};
lli B[200005] = {};
lli C[200005] = {};

int main() {
	lli N;
	cin >> N;

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

	lli S = 0;
	for (lli i = 1; i <= N; i++) {
		S += (B[i] * (B[i] - 1)) / 2;
	}

	for (lli i = 1; i <= N; i++) {
		cout << S - (B[A[i]] - 1) << endl;
	}

	return 0;
}

Measured memory_bytes: 5376
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

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

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

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

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

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

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

fn main() {
    input! {
        n: usize,
        k: usize,
    };
    let mut ret = 0.0;
    for i in 1..(n + 1) {
        let mut temp = 1.0 / (n as f64);
        let mut now = i;
        while now < k {
            temp /= 2.0;
            now *= 2;
        }
        ret += temp;
    }
    println!("{}", ret);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define meow(args...) fprintf(stderr, args)
typedef unsigned u32;
typedef long long s64;
typedef unsigned long long u64;
template<class T1, class T2> inline bool cmin(T1 &a, const T2 &b) {return b<a?(a=b, true):false;}
template<class T1, class T2> inline bool cmax(T1 &a, const T2 &b) {return a<b?(a=b, true):false;}
template<class Type> Type read() {
	Type a;
	bool b;
	unsigned char c;
	while(c=getchar()-48, (c>9)&(c!=253));
	for(a=(b=c==253)?0:c; (c=getchar()-48)<=9; a=a*10+c);
	return b?-a:a;
}
int (*rd)()=read<int>;

const int N=2e5+1;
int n, p[N], root[N], cnt[N][2], l[N], r[N];
s64 ans;
bool less(int *x, int *y) {
	return (s64)x[1]*y[0]<(s64)x[0]*y[1];
}
int merge(int u, int v) {
	if(u==0||v==0) return u+v;
	if(less(cnt[v], cnt[u])) std::swap(u, v);
	l[u]=merge(l[u], v);
	std::swap(l[u], r[u]);
	return u;
}
int main() {
	n=rd();
	for(int i=2; i<=n; ++i) p[i]=rd();
	for(int i=1; i<=n; ++i) cnt[i][rd()]=1;
	for(int i=n; i>=1; --i) {
		while(root[i]&&less(cnt[root[i]], cnt[i])) {
			ans+=(s64)cnt[i][1]*cnt[root[i]][0];
			cnt[i][0]+=cnt[root[i]][0];
			cnt[i][1]+=cnt[root[i]][1];
			root[i]=merge(l[root[i]], r[root[i]]);
		}
		root[i]=merge(i, root[i]);
		if(i!=1) root[p[i]]=merge(root[i], root[p[i]]);
	}
	int s=0;
	while(root[1]) {
		ans+=(s64)s*cnt[root[1]][0];
		s+=cnt[root[1]][1];
		root[1]=merge(l[root[1]], r[root[1]]);
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 4992
//#define frostbyte02
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=a; i<=b; i++)
#define LLFOR(i,a,b) for (ll i=a; i<=b; i++)
#define REP(i,a,b) for (int i=a; i<b; i++)
#define FORD(i,a,b) for (int i=a; i>=b; i--)
#define fi first
#define se second
#define pb push_back
#define fastio {ios_base::sync_with_stdio(false); cin.tie(0);}
#define sqr(x) (x)*(x)
#define sqrmod(x) (((x)%MOD)*((x)%MOD))%MOD

using namespace std;
const int MOD = 1e9+7;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;

int main()                                
{
#ifdef frostbyte02
        freopen("input.txt","r",stdin);
        //freopen("output.txt","w",stdout);
#endif
        fastio
        int a, b, c; cin >> a >> b >> c;
        if ((c<=b && c>=a) || (c<=a && c>=b)) cout << "Yes";
        else cout << "No";
        return 0;  
}


Measured memory_bytes: 256
#include <stdio.h>
 
int main(){
 int A,B,C,D;
  scanf("%d %d %d %d",&A,&B,&C,&D);
  
  while(A-D > 0 && C-B > 0){
  int E,F;
    E = C - B;
    F = A - D;
    C = E;
    A = F;
  }
  
  if ( C - B <= 0){
  printf("Yes");
  }
  
  else if ( A - D <= 0){
  printf("No");
  }
}

Measured memory_bytes: 1736
#include<iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long int lli;
lli waru(lli k,lli x){
    if(k != -1){
      return k / x + 1;
    }else{
      return 0;
    }
}

int main(){
  lli a,b,x;
  lli count = 0;
  cin >> a >> b >> x;
  count = waru(b,x) - waru(a-1,x);
  cout << count << endl;
}

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    const uint64_t maxOne{1000000000000001};
    uint64_t n;
    cin >> n;
    uint64_t base = 26;
    uint64_t sum = 26;
    uint64_t lastBase = 0;
    int k = 1;
    while(n > sum){
        lastBase = base;
        base = base*26;
        sum += base;
        k++;
    }
    uint64_t delta = n-(sum-base)-1;
    string str(k, 'a');
    int pos = k-1;
    while(delta > 0){
        str[pos] = delta%26 + 'a';
        pos--;
        delta = delta/26;
    }
    cout << str << endl;

    
    return 0;
}

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

int main() {
	int A,B;
  	cin >> A >> B;
  
  	bool can = true;
  	if(A + B > 16) can = false;
  
  	int sa = abs(A - B);
  	int rest = 16 - 2 * min(A,B);
  
  	if(sa * 2 > rest) can = false;
  
  	if(can) {
    	cout << "Yay!" << endl;
    }else {
    	cout << ":(" << endl;
    }
}

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

using ll = long long;

const int INF = 1001001001;
const ll INF_LL = 1001001001001001001LL;

int main(void){
  int n; cin >> n;
  vector<pair<int,int>> a;

  for(int i = 1;i<=n;i++){
    int cnt;
    cin >> cnt;
    a.emplace_back(cnt,i);
  }
  sort(a.begin(),a.end());

  for(auto x : a){
    int ans = x.second;
    cout << ans << " ";
  }
  cout << endl;
  
  return 0;
}


Measured memory_bytes: 4280
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>

#define PI (3.1415926535898)

int main(void) {

	int n;
	int s[1000];
	double total;
	for(;;) {
		total = 0;
		scanf("%d", &n);
		if (n == 0) {
			break;
		}

		double m = 0;
		for (int i = 0; i < n; i++) {
			scanf("%d", &s[i]);
			m = m + s[i];
		}
		double ave = m / n;

		for (int i = 0; i < n; i++) {
			double tmp =  (s[i] - ave) * (s[i] - ave);
			total += tmp;
		}

		double hensa = sqrt(total / (double)n);
		printf("%lf\n", hensa);

	}

}

Measured memory_bytes: 2756
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(), x.end()
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
using namespace std;
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const ll inf = 1e9;
const int MAX_N = 500;

int main() {
    int a, b; cin >> a >> b;
    if (a > 8 || b > 8) cout << ":(" << endl;
    else cout << "Yay!" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 510000;
const int MOD = 1000000007;

/*long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}*/
int main() {
  int N;
  cin >> N;
  vector<ll> A(N);

  for (int i = 0; i < N; i++)
  {
      /* code */
      cin >> A[i];
  }

  map<ll, int> p;

  for (int i = 0; i < N; i++)
  {
      p[A[i]] += 1;
  }
  
  bool hantei = false;
  vector<ll> g;
  vector<ll> t;
  ll ans = 0;
  for(auto i : p) {
     
      if (i.second > 1) { g.push_back(i.first); }
      if (i.second >= 4) { t.push_back(i.first); }
  }
  if(g.size() < 2) { cout << 0 << endl; return 0; }
  sort(g.begin(), g.end());
  reverse(g.begin(), g.end());
  ans = g[0] * g[1];
  for (auto i : t) {
      if ( ans < i * i) ans = i * i;
  }
  cout << ans << endl;

    return 0;
}

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

#define pb push_back
#define lli long long int
int bingo [3][3];

void mark (int aux)
{
    for (int i = 0 ; i < 3 ; i++)
    {
        for (int j = 0 ; j < 3 ; j++)
        {
            if (bingo[i][j] == aux)
            {
                bingo[i][j] = INT_MIN ;
                return ;
            }
        }
    }
}
bool verify ()
{
    if (bingo[0][0] == INT_MIN && bingo[0][1] == INT_MIN  && bingo[0][2] == INT_MIN )
    {
        return true ;
    }
    else if (bingo[1][0] == INT_MIN && bingo[1][1] == INT_MIN  && bingo[1][2] == INT_MIN )
    {
        return true ;
    }
    else if (bingo[2][0] == INT_MIN && bingo[2][1] == INT_MIN  && bingo[2][2] == INT_MIN )
    {
        return true ;
    }
    else if (bingo[0][0] == INT_MIN && bingo[1][0] == INT_MIN  && bingo[2][0] == INT_MIN )
    {
        return true ;
    }
    else if (bingo[0][1] == INT_MIN && bingo[1][1] == INT_MIN  && bingo[2][1] == INT_MIN )
    {
        return true ;
    }
    else if (bingo[0][2] == INT_MIN && bingo[1][2] == INT_MIN  && bingo[2][2] == INT_MIN )
    {
        return true ;
    }
    else if (bingo[0][0] == INT_MIN && bingo[1][1] == INT_MIN  && bingo[2][2] == INT_MIN )
    {
        return true ;
    }
    else if (bingo[0][2] == INT_MIN && bingo[1][1] == INT_MIN  && bingo[2][0] == INT_MIN )
    {
        return true ;
    }
    else 
    {
        return false ;
    }
}
int main()
{   
    for (int i = 0 ; i < 3 ; i++)
    {
        for (int j = 0 ; j < 3 ; j++)
        {
            cin >> bingo [i][j] ;
        }
    }

    int q , aux ;
    cin >> q ;
    
    while (q--)
    {
        cin >> aux ;
        mark (aux);
    }

    if (verify())
    {
        cout << "Yes\n";
    }
    else
    {
        cout << "No\n";
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <bitset>
#include <cmath>
#define REP(i,n) for(int i=0;i<(n);++i)
using namespace std;
typedef long long LL;

int main() {
  int A, B, C;
  cin >> A >> B >> C;
  cout << C << " " << A << " " << B << endl;
} 

Measured memory_bytes: 256
/*{{{*/
#include <bits/stdc++.h>
#ifdef _GLIBCXX_DEBUG
int c_;
#define cout (c_?cerr:cout)
#define debug(...) {if(!c_)cerr<<"\033[96;1m";++c_;\
__VA_ARGS__;--c_; if(!c_)cerr<<"\033[0m";}
#else
#define debug(...)
#endif
#define st first
#define nd second
#define all(...) (__VA_ARGS__).begin(), (__VA_ARGS__).end()
#define dump(...) debug(print(#__VA_ARGS__, '=',  __VA_ARGS__))
#define dump_range(...) debug(cerr<<#__VA_ARGS__<<": ";print_range(__VA_ARGS__))
using namespace std; using ll = long long; 
template< typename t > using V = vector< t >; void print(){cout<<'\n';}
template< typename t, typename... v > void print(const t& a, v&&... b)
{cout << a << (sizeof...(b)? " " : ""); print(b...);}
template< typename t > void print_range(t a, const t& b)
{while (a!=b) cout << (*a++) << ' '; cout << '\n';}
/*}}}*/

constexpr int nax = 1e5, mod = 1e9 + 7;

int n, tb[nax + 1];

int fpow(int v, int w)
{
    int r = 1;
    while (w)
    {
        if (w & 1) r = ((ll)r * v) % mod;
        v = ((ll)v * v) % mod;
        w >>= 1;
    }
    return r;
}

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

    cin >> n;

    for (int i = 1; i <= n; ++i)
        tb[i] = fpow(i, mod - 2);

    dump_range(tb, tb + n + 1);

    tb[1] = 0;

    for (int i = 3; i <= n; ++i)
        tb[i] = (tb[i] + tb[i - 1]) % mod;

    int rs = 0;

    for (int i = 0; i < n; ++i)
    {
        int v; cin >> v;
        int q = (tb[i + 1] + tb[n - i - 1 + 1]) % mod;
        ++q; if (q == mod) q = 0;
        q = ((ll)q * v) % mod;
        rs = (rs + q) % mod;
    }

    for (int i = 1; i <= n; ++i)
        rs = ((ll)rs * i) % mod;

    print(rs);
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define MOD 1000000007
#define pb push_back
using namespace std;
const int nmax=112345;

int n,h[nmax],cnt[nmax];

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;++i)
        scanf("%d",&h[i]);
    cnt[1]=abs(h[1]-h[0]);
    for(int i=2;i<n;++i)
        cnt[i]=min(cnt[i-2]+abs(h[i]-h[i-2]),cnt[i-1]+abs(h[i]-h[i-1]));
    printf("%d",cnt[n-1]);

    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>

struct Coordinate {
	int x, y;
};
void swap(std::vector<std::string>& state, const Coordinate a, const Coordinate b) {
	auto temp = state[a.y][a.x];
	state[a.y][a.x] = state[b.y][b.x];
	state[b.y][b.x] = temp;
}
void drop(std::vector<std::string>& state) {
	for (auto i = 0; i < state.front().size(); ++i) {
		int count = 1;
		for (auto j = 1; j <= state.size(); ++j) {
			if (state[state.size() - j][i] != '.') {
				if (count != j) {
					swap(state, { i, (int)state.size() - count }, { i, (int)state.size() - j });
				}
				++count;
			}
		}
	}
}
bool erase(std::vector<std::string>& state, const int n) {
	bool is_erase = false;
	std::vector<std::vector<bool>> erase_horizontal(state.size(), std::vector<bool>(state.front().size(), false));
	for (auto i = 0; i < state.size(); ++i) {
		int len = 1;
		for (auto j = 1; j < state[i].size(); ++j) {
			if (state[i][j] != '.' && state[i][j] == state[i][j - 1]) ++len;
			else len = 1;
			erase_horizontal[i][j] = len >= n;
		}
	}
	for (auto j = 0; j < state.front().size(); ++j) {
		int len = 1;
		for (auto i = 1; i < state.size(); ++i) {
			if (state[i][j] != '.' && state[i][j] == state[i - 1][j]) ++len;
			else {
				if (len >= n) {
					is_erase = true;
					for (auto y = i - len - 1; len > 0; --len) {
						state[y + len][j] = '.';
					}
				}
				len = 1;
			}
		}
		if (len >= n) {
			is_erase = true;
			for (auto y = state.size() - len - 1; len > 0; --len) {
				state[y + len][j] = '.';
			}
		}
	}
	for (auto i = 0; i < state.size(); ++i) {
		for (auto j = 1; j < state[i].size(); ++j) {
			if (erase_horizontal[i][j]) {
				is_erase = true;
				if (erase_horizontal[i][j - 1]) {
					state[i][j] = '.';
				}
				else {
					for (auto y = j - n + 1; y <= j; ++y) {
						state[i][y] = '.';
					}
				}
			}
		}
	}
	return is_erase;
}
bool is_all_erased(std::vector<std::string> state, const Coordinate a, const Coordinate b, const int n) {
	swap(state, a, b);
	do {
		drop(state);
	} while (erase(state, n));
	return std::all_of(state.begin(), state.end(), [](const std::string& str) {return std::all_of(str.begin(), str.end(), [](const char c) {return c == '.'; }); });
}
int main() {
	int h, w, n; std::cin >> h >> w >> n;
	std::vector<std::string> state(h); for (auto& line : state) std::cin >> line;
	for (auto i = 0; i < h; ++i) {
		for (auto j = 1; j < w; ++j) {
			if (is_all_erased(state, { j, i }, { j - 1, i }, n)) {
				std::cout << "YES\n"; 
				return 0;
			}
		}
	}
	std::cout << "NO\n";
}



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

using namespace std;

#ifdef WIN32
	#define I64 "%I64d"
#else
	#define I64 "%lld"
#endif

typedef long long ll;

#define f first
#define s second
#define mp make_pair
#define pb push_back
#define all(s) s.begin(), s.end()
#define sz(s) (int(s.size()))
#define fname "a"

vector <int> a;

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

	ll n;
	cin >> n;
	int res = 0;
	for (ll i = n; i; i /= 10) {
		res += i % 10;
		a.pb(i % 10);
	}

	reverse(all(a));
	for (int i = 0; i < sz(a); ++i) {
		res = max(res, a[i] - 1 + (sz(a) - 1 - i) * 9);
	}

	cout << res << endl;

	return 0;
}


Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ff first
#define ss second
typedef long long ll;
ll power(ll a, ll b){//a^b
    ll res=1;
    a=a%MOD;
    while(b>0){
        if(b&1){res=(res*a)%MOD;b--;}
        a=(a*a)%MOD;
        b>>=1;
    }
    return res;
}
ll fermat_inv(ll y){return power(y,MOD-2);}
ll gcd(ll a, ll b){return (b==0)?a:gcd(b,a%b);}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t=1;
    //cin>>t;
    while(t--){
        string s;
        cin>>s;
        int n=s.length();
        int val=0;
        for(int i=0;i<n;i++){
            val+=(s[i]-'0');
        }
        val=val%9;
        if(val==0)
            cout<<"Yes\n";
        else
            cout<<"No\n";
    }
    return 0;
}

Measured memory_bytes: 3748
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define lca long long
using namespace std;

lca h;

int main()
{
    scanf("%lld", &h);
    lca ans = 1ll;
    lca res = 1ll;
    while(h!=1)
    {
        h /= 2;
        res *= 2;
        ans += res;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
n,m = [int(i) for i in input().split()]
dict1 = {}
if n!=1:
    dict1[1]=1
else:
    dict1[1]=0
for i in range(1,n):
    dict1[i+1]=0
list1 = []
for i in range(m):
    si,mi = [int(i)for i in input().split()]
    if si==1 and mi==0 and n!=1:
        print(-1)
        break
    if not(si in list1):
        dict1[si]=mi
    else:
        if mi!=dict1[si]:
            print(-1)
            break
    list1.append(si)
else:
    num = ""
    for i in range(1,n+1):
        num+=str(dict1[i])
    print(int(num))

Measured memory_bytes: 3064
from queue import Queue

def main():
    N, Q = map(int, input().split())
    q = Queue()
    for n in range(N):
        name, time = input().split()
        q.put((name, int(time)))
    
    timer = 0
    while not q.empty():
        name, time = q.get()
        if time > Q:
            time -= Q
            timer += Q
            q.put((name, time))
        else:
            timer += time
            print("{} {}".format(name, timer))
            
            
if __name__=="__main__":
    main()


Measured memory_bytes: 13376
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#include<set> 
#include<math.h>
#define pai arccos(-1);
#define keta(n) cout << fixed << setprecision((n));
#define ll long long;

int main(){
  int n,l;
  cin>>n>>l;
  vector<string> s(n);
  rep(i,n)cin>>s[i];
  sort(s.begin(),s.end());
  rep(i,n){
    cout<<s[i];
  }
  
}


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

short table[1000][1000];

int main(){

    int c,n,ans=0,N,count=0;
    char cha;

    cin >> c >> n;

    N = n-1;

    for(int i=0; i<n; i++){
      for(int j=0; j<n; j++){
          cin >> cha;
          table[i][j] = (cha=='0') ? 0 : 1;
      }
    }

    for(int i=0; i<n/2; i++){
      for(int j=0; j<n/2; j++){
          if( (table[i][j] + table[i][N-j] + table[N-i][j] + table[N-i][N-j]) % 4 != 0){
            count++;
          }
      }
    }

    if(count==0){
      ans++;
    }

    int d,w,h;

    while(--c){

      bool beforeok;

      cin >> d;

      for(int i=0;i<d;i++){
        cin >> w >> h;
        w--;
        h--;
        if( (table[w][h] + table[w][N-h] + table[N-w][h] + table[N-w][N-h]) % 4 != 0){
          beforeok = false;
        }else{
          beforeok = true;
        }
        table[w][h] = (table[w][h] == 0) ? 1 : 0;

        if( (table[w][h] + table[w][N-h] + table[N-w][h] + table[N-w][N-h]) % 4 != 0){
          if(beforeok){
            count++;
          }
        }else{
          count--;
        }

      }

      if(count==0){
        ans++;
      }

    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 5016
#include <iostream>

using namespace std;

int* A;
int n;

bool solve(int i, int m){
    if(m == 0){
        return true;
    }else if(i >= n){
        return false;
    }else{
        return solve(i + 1, m) || solve(i + 1, m - A[i]);
    }
}

int main() {
    cin >> n;
    
    A = new int[n];
    for(int i = 0; i < n; ++i){
        cin >> A[i];
    }
    
    int q;
    cin >> q;
    
    int m[q];
    for(int i = 0; i < q; ++i){
        cin >> m[i];
    }
    
    for(int i = 0; i < q; ++i){
        if(solve(0, m[i])){
            cout << "yes" << endl;
        }else{
            cout << "no" << endl;
        }
    }
    
    return 0;
}

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

#define ALL(v) v.begin(), v.end()
#define V vector
#define P pair
using ll = long long;
using ld = long double;
const int MOD = 1e9+7;


int main() {
    int n; cin >> n;
    if(n < 1000) cout << "ABC" << endl;
    else cout << "ABD" << endl;

    return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define rep(i, z, n) for(int i = z; i < n; i++)
#define all(v) v.begin(), v.end()
typedef long long ll;
//const int INF = 1<<29;
//const int MODINF = 1000000007;
using namespace std;

int main(){
    int X;
    cin >> X;
    int ans = 0;
    int time = 0;
    while(ans < 2 * X){
        time++;
        ans = time * (time + 1);
    }
    cout << time << endl;
}

Measured memory_bytes: 256
import collections
N = int(input())
S = int(input())

if N == S:
    print(N + 1)
    exit()


def prime_decomposition(n):
    i = 2
    ret = collections.defaultdict(int)
    while i * i <= n:
        while n % i == 0:
            n //= i
            ret[i] += 1
        i += 1
    if n > 1:
        ret[n] = 1
    return ret


def digitsum(x, f):
    if x < f:
        return x
    else:
        return x % f + digitsum(x // f, f)


fs_dict = prime_decomposition(N - S)
fs_set = set([1])

for p, n in fs_dict.items():
    fs_set_copy = fs_set.copy()
    for i in range(1, n + 1):
        for x in fs_set_copy:
            fs_set.add(x * p**i)
for f in sorted(fs_set):
    f += 1
    if digitsum(N, f) == S:
        print(f)
        exit()
else:
    print(-1)


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

int main() {
  int W,H,x,y;
  cin >> W >> H >> x >> y;
  
  int ans = 0;
  if((x == W / 2.0) && (y == H / 2.0)) ans = 1;
  
  cout << (double)W * H / 2.0 << " " << ans << endl;
  return 0;
}



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

const int BITS = 29;

int N;
vector<int> A, B;

void sort_by_bit(vector<int> &numbers, int bit) {
    vector<int> new_numbers(N);
    int start = 0, end = N;

    for (int number : numbers)
        if (number >> bit & 1)
            new_numbers[--end] = number;
        else
            new_numbers[start++] = number;

    assert(start == end);
    reverse(new_numbers.begin() + start, new_numbers.end());
    numbers = new_numbers;
    assert(is_sorted(numbers.begin(), numbers.end(), [&](int a, int b) {
        return (a & ((2 << bit) - 1)) < (b & ((2 << bit) - 1));
    }));
}

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

    cin >> N;
    A.resize(N);
    B.resize(N);

    for (int &a : A)
        cin >> a;

    for (int &b : B)
        cin >> b;

    int answer = 0;

    for (int bit = 0; bit < BITS; bit++) {
        long long ones = 0;
        int full = (1 << bit) - 1;

        for (int i = 0, j = N; i < N; i++) {
            while (j > 0 && (A[i] & full) + (B[j - 1] & full) > full)
                j--;

            ones += N - j;
        }

        long long a_ones = 0, b_ones = 0;

        for (int i = 0; i < N; i++) {
            a_ones += A[i] >> bit & 1;
            b_ones += B[i] >> bit & 1;
        }

        ones += N * (a_ones + b_ones);

        if (ones % 2 != 0)
            answer |= 1 << bit;

        sort_by_bit(A, bit);
        sort_by_bit(B, bit);
    }

    cout << answer << '\n';
}


Measured memory_bytes: 2672
s = input()
r = 1000
j = 0
for i in range(len(s) - 2):
    if abs(int(s[i:i + 3]) - 753) < r:
        r = abs(int(s[i:i + 3]) - 753)
        j = i
print(abs(int(s[j:j + 3])-753))


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

using namespace std;

#define INF 1000007
#define MOD 1000000007
#define maxn 100
#define int long long int
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, n) FOR(i, 0, n)

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

int mpow(int N, int P, int M) //繰り返し自乗法
{
    if (P == 0)
        return 1;
    if (P % 2 == 0)
    {
        int t = mpow(N, P / 2, M);
        return t * t % M;
    }
    return N * mpow(N, P - 1, M) % M;
}

int counter(int x)
{ //bit計算
    if (x == 0)
        return 0;
    return counter(x >> 1) + (x & 1);
}

vector<bool> prime(maxn + 1, true); //素数テーブル
void prime_table(void)
{
    prime[0] = false;
    prime[1] = false;
    for (int i = 2; i * i <= maxn; i++)
    {
        if (!prime[i])
        {
            continue;
        }
        for (int j = i + i; j <= maxn; j += j + i)
        {
            prime[j] = false;
        }
    }
}

int N, M;
vector<string> A, B;
bool check(int x, int y)
{
    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (B[i][j] != A[y + j][x + i])
            {
                return false;
            }
        }
    }
    return true;
}
signed main()
{
    cin >> N >> M;
    rep(i, N)
    {
        string a;
        cin >> a;
        A.push_back(a);
    }
    rep(i, M)
    {
        string b;
        cin >> b;
        B.push_back(b);
    }
    for (int i = 0; i <= N - M; i++)
    {
        for (int j = 0; j <= N - M; j++)
        {
            if (check(i, j))
            {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;
import java.util.ArrayList;

public class Main {
	public static void main (String[] args) {
  Scanner sc = new Scanner(System.in);
  int h = sc.nextInt();
  int w = sc.nextInt();
  ArrayList<String> x = new ArrayList<String>();
  for(int i=0; i<h; i++){
    x.add(sc.next());
  }
  for(int j=0; j<h+2; j++){
    if(j==0 || j==h+1){
	for(int k=0; k<w+2; k++){
		System.out.print("#");
	}
        System.out.println("");
    }else{
	System.out.println("#" + x.get(j-1) + "#");
    }
}
}
}

Measured memory_bytes: 22484
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using Pll = pair<ll, ll>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(v) v.begin(), v.end()
#define sz(x) ((int) x.size())
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
const int MOD = 1e9+7;
const int INF = 2e9;
template<class T> void print(const T& t){ cout << t << endl; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main(){
  ll n,m;
  cin >> n >> m;
  vi c(n, 0);
  rep(i,m){
    ll a, b;
    cin >> a >> b;
    c[a - 1]++;
    c[b - 1]++;
  }
  rep(i,n){
    print(c[i]);
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  string num1, num2;
  cin >> num1 >> num2;
  if(num1.size() > num2.size()) {
  	cout << "GREATER";
  } else if(num1.size() < num2.size()) {
  	cout << "LESS";
  } else {
    bool isEq = true;
    for(int i = 0; i < num1.size() && isEq; ++i) {
    	if(num1[i] > num2[i]) {
          cout << "GREATER";
          isEq = false;
        } else if(num1[i] < num2[i]) {
          cout << "LESS";
          isEq = false;
        }
    }
    if(isEq) {
      cout << "EQUAL";
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define SELECTER(_1, _2, _3, SELECT, ...) SELECT
#define REP1(i, n) for(int (i)=0; (i)<(n); (i)++)
#define REP2(i, a, b) for(int (i)=(a); (i)<(b); (i)++)
#define REP(...) SELECTER(__VA_ARGS__, REP2, REP1,) (__VA_ARGS__)
#define MOD 1000000007

template <class T> ostream& operator<<(ostream& os, const vector<T>& v){ os << "{"; for(size_t i=0; i<v.size(); i++) os << v[i] << (i+1==v.size() ? "" : ", "); os << "}"; return os; }
template <class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p){ return os << "{" << p.first << ", " << p.second << "}"; }

vector<int> calc(string &S, int N, int C){
    vector<int> ret(N+1);
    int cur = 0, last=-(1<<30);
    for(int i=0; i<N; i++){
        if(S[i] == 'x'){
            ret[i+1] = cur;
            continue;
        }
        if(i < last+C+1) ret[i+1] = cur;
        else{
            cur++;
            ret[i+1] = cur;
            last = i;
        }
    }
    return ret;
}

int main(){
    int N, K, C;
    string S;
    cin >> N >> K >> C >> S;
    string T = S;
    reverse(T.begin(), T.end());
    auto L = calc(S, N, C);
    auto R = calc(T, N, C);
    for(int i=0; i<N; i++){
        if(L[i]+R[N-1-i]<K) cout << i+1 << endl;
    }
    return 0;
}



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

using namespace std;


int main() {
	int n, minv = 2000000;
	string s;
	cin >> n >> s;
	int bc = 0, wc = 0, bbc, bwc;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '.') {
			bc++;
		}
	}
	bbc = bc;
	bwc = s.size() - bc;

	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '#') {
			wc++;
		}
		else {
//			if(i!=0)
				bc--;
		}
		if (minv > wc + bc) {
			minv = bc + wc;
		}
	}


	cout << min(minv,min(bbc,bwc)) << endl;

	return 0;
}

//
//9
//.###..#..#..##..#..

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

using namespace std;
int n,k,a[60],h;
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	sort(a+1,a+1+n);
	for(int i=n;i>n-k;i--)
	h+=a[i];
	cout<<h<<endl;
	
	return 0;
}

Measured memory_bytes: 256
use std::io::prelude::*;

fn input<T>() -> T
where
    T: std::str::FromStr,
{
    let stdin = std::io::stdin();
    let token = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    token.parse().ok().unwrap()
}

fn main() {
    let a = input::<i64>();
    let b = input::<i64>();
    let q = input::<i64>();
    let s = (0..a).map(|_| input()).collect::<Vec<i64>>();
    let t = (0..b).map(|_| input()).collect::<Vec<i64>>();
    let x = (0..q).map(|_| input()).collect::<Vec<i64>>();

    let ans = x.iter().map(|x| calc(&s, &t, *x)).collect::<Vec<i64>>();
    let out = std::io::stdout();
    let mut buf = std::io::BufWriter::new(out.lock());
    for an in ans {
        writeln!(buf, "{}", an).unwrap();
    }
}

fn calc(s: &Vec<i64>, t: &Vec<i64>, x: i64) -> i64 {
    let mut ans = std::i64::MAX;

    for i in 0..2 {
        let pos0 = match s.binary_search(&x) {
            Ok(p) => s[p],
            Err(p) => {
                if p == 0 {
                    s[p]
                } else if p == s.len() {
                    s[p - 1]
                } else {
                    s[p - 1 + i]
                }
            }
        };

        for j in 0..2 {
            let pos1 = match t.binary_search(&pos0) {
                Ok(p) => t[p],
                Err(p) => {
                    if p == 0 {
                        t[p]
                    } else if p == t.len() {
                        t[p - 1]
                    } else {
                        t[p - 1 + j]
                    }
                }
            };

            let d = i64::abs(x - pos0) + i64::abs(pos0 - pos1);
            ans = std::cmp::min(ans, d);
        }
    }

    for i in 0..2 {
        let pos0 = match t.binary_search(&x) {
            Ok(p) => t[p],
            Err(p) => {
                if p == 0 {
                    t[p]
                } else if p == t.len() {
                    t[p - 1]
                } else {
                    t[p - 1 + i]
                }
            }
        };

        for j in 0..2 {
            let pos1 = match s.binary_search(&pos0) {
                Ok(p) => s[p],
                Err(p) => {
                    if p == 0 {
                        s[p]
                    } else if p == s.len() {
                        s[p - 1]
                    } else {
                        s[p - 1 + j]
                    }
                }
            };

            let d = i64::abs(x - pos0) + i64::abs(pos0 - pos1);
            ans = std::cmp::min(ans, d);
        }
    }

    ans
}


Measured memory_bytes: 9468
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repp(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define rrep(i, n, m) for (int i = n; i >= m; i--)
#define p(a,b) printf(a,b);
#define o(s) cout<< s << endl;
typedef long long LL;
template <class T>
bool contain(const std::string &s, const T &v)
{
    return s.find(v) != std::string::npos;
}

int main()
{
    int n,h,w; cin>>n>>h>>w;
    o((n-h+1)*(n-w+1));
}


Measured memory_bytes: 256
#include <stdio.h>
long long int pavan(long long int a,long long int b)
{
  if(a==0)
  {
    return b;
  }
  if(b==0)
  {
    return a;
  }
  pavan(b%a,a);
}
long long int main()
{
  long long int a,b;
  scanf("%lld %lld",&a,&b);
  printf("%lld\n",(a*b)/(pavan(a,b)));
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
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(a > b){ a = b; return 1; } return 0; }
typedef long long ll;
template <typename X = int>
struct Edge{
  int from;
  int to;
  X cost;

  Edge() = default;

  Edge(int from, int to, X cost = 1) : from(from), to(to), cost(cost) {}
};

template <typename X = int>
struct Node{ // priority_queueに入れる頂点の情報
  int idx;
  X dis;

  Node() = default;

  Node(int idx, X dis) : idx(idx), dis(dis) {}
  
  bool operator == (const Node& r) const {
    return (idx == r.idx && dis == r.dis); 
  }

  bool operator != (const Node& r) const {
    return !(*this == r);
  }

  bool operator < (const Node& r) const {
    return dis > r.dis;
  }

  bool operator > (const Node& r) const {
    return dis < r.dis;
  }  
};

template <typename X = int>
class Graph{
private:
  int n;
  int m;
  vector<vector<Edge<X>>> edge;
  vector<vector<X>> d;
  X inf = 1e+17;
  
public:
  Graph(int n) : n(n) {
    edge.resize(n);
  }

  Graph(int n, int m, vector<int> a, vector<int> b, vector<X> c) : n(n), m(m){
    edge.resize(n);
    rep(i,m) {
      add_edge(a[i], b[i], c[i]);
      add_edge(b[i], a[i], c[i]);
    }
  }

  void add_edge(int from, int to, X cost = 1) {
    edge[from].emplace_back(from, to, cost);
  }

  void dijkstra(int s) {
    d.resize(n);
    d[s].resize(n ,inf);
    d[s][s] = 0;
    //    using pi = pair<int, X>;    
    //    auto compare = [](pi a, pi b) { return a.second < b.second; };
    //    priority_queue<pi, vector<pi>, decltype(compare)> pq{compare};
    priority_queue<Node<X>> pq;
    pq.emplace(s, 0);
    while( !pq.empty() ) {
      Node<X> p = pq.top(); pq.pop();
      int v = p.idx; // 頂点
      X dist = p.dis; // s->vの最短距離
      if(d[s][v] < dist) continue;
      for(auto w: edge[v]) {
	if(chmin(d[s][w.to], d[s][v] + w.cost)) {
	  pq.emplace(w.to, d[s][w.to]);
	}
      }
    }
  }

  X get_d(int u, int v) { return d[u][v]; }
  X get_inf() { return inf; }
  
};

int main()
{
  int n,m,s,t;cin >> n >> m >> s >> t;
  s--; t--;
  vector<int> u(m), v(m);
  vector<ll> a(m), b(m);
  rep(i,m) {
    cin >> u[i] >> v[i] >> a[i] >> b[i];
    u[i]--; v[i]--;
  }

  Graph<ll> gpen(n, m, u, v, a);
  Graph<ll> gpsn(n, m, u, v, b);

  gpen.dijkstra(s);
  gpsn.dijkstra(t);

  vector<ll> res(n);
  rep(i,n) {
    res[i] = gpen.get_d(s, i) + gpsn.get_d(t, i);
  }

  ll M = 1e+15;
  ll tmp = M;
  vector<ll> ans(n);
  for(int i = n - 1;i >= 0;--i) {
    tmp = min(tmp, res[i]);
    ans[i] = M - tmp;
  }

  rep(i,n) cout << ans[i] << "\n";
  
  return 0;
}


Measured memory_bytes: 26976
using System;
using System.Collections.Generic;
using System.Linq;
class Ho{
  static void Main(){
   var ez = Console.ReadLine().Split();
   var s = int.Parse(ez[0]);
   var w = int .Parse(ez[1]);
   if(w >= s) {Console.WriteLine("unsafe");}
   else {Console.WriteLine("safe");}

  }
}

Measured memory_bytes: 17864
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int u32;
typedef pair<int, int> p;
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; }
int Inf = (1<<30);
ll inf = (1LL<<60);
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
int main(){ // めっちゃ難しく考えてた
	int a, b;
	cin >> a >> b;
	int c, d;
	cin >> c >> d;
	int e;
	cin >> e;
	int f;
	cin >> f;
	int i, j, k, l;
	int ans1 = 100 * a;
	int ans2 = 0;
	for (i = 0; 100 * i * a <= f; i++) {
		int A = 100 * i * a;
		for (j = 0; 100 * j * b <= f - A; j++) {
			int B = 100 * j * b;
			for (k = 0; k <= f - A - B; k++) {
				int C = k * c;
				for (l = 0; l <= f - A - B - C; l++) {
					int W = A + B;
					if (W > f) continue;
					int S = C + l * d;
					if (W + S > f || W / 100 * e < S) continue;
					double ans = (double)ans2 / double(ans1);
					double tmp = (double)S / (double)(W + S);
					if (ans < tmp) {
						ans1 = W + S;
						ans2 = S;
					}
				}
			}
		}
	}
	cout << ans1 << " " << ans2;
	return(0);
}

Measured memory_bytes: 256
using System;
class Program
{
    static void Main()
    {
        const int MAX = 30;
        const int SWAP = 2;
        int[] lots = new int[MAX];
        int[] nums = new int[SWAP];
        int vert = int.Parse(Console.ReadLine());
        for (int i = 0; i < vert; ++i)
        {
            lots[i] = i + 1;
        }
        int hori = int.Parse(Console.ReadLine());
        for (int i = 0; i < hori; ++i)
        {
            string[] command = Console.ReadLine().Split(',');
            nums[0] = int.Parse(command[0]) - 1;
            nums[1] = int.Parse(command[1]) - 1;

            int tmp = lots[nums[0]];
            lots[nums[0]] = lots[nums[1]];
            lots[nums[1]] = tmp;
        }
        for (int i = 0; i < vert; ++i)
        {
            Console.Out.WriteLine(lots[i]);
        }
    }
}


Measured memory_bytes: 15952
object Main extends App {

  val s = scala.io.StdIn.readLine()


  def solve() =  {
    val first = s.splitAt(2)._1.toInt
    val second = s.splitAt(2)._2.toInt

    (isMonth(first), isMonth(second)) match {
      case (true,  true)  => "AMBIGUOUS"
      case (false, true)  => "YYMM"
      case (true,  false) => "MMYY"
      case (false, false) => "NA"
    }
  }

  def isMonth(num: Int) = {
    if(1 <= num && num <= 12) true else false
  }


  println(solve)

}

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

int value[128];

void init() {
	value['I'] = 1;
	value['V'] = 5;
	value['X'] = 10;
	value['L'] = 50;
	value['C'] = 100;
	value['D'] = 500;
	value['M'] = 1000;
}

int main() {
	init();

	string number;
	while(cin >> number) {
		int res = 0;

		for(unsigned i = 0; i < number.size(); ++i) {
			if(i + 1 < number.size() && value[number[i]] < value[number[i + 1]]) {
				res -= value[number[i]];
			}
			else {
				res += value[number[i]];
			}
		}

		cout << res << endl;
	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 1184
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<int, lint> pil;
typedef pair<lint, int> pli;
typedef pair<lint, lint> pll;
template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T> bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}
template<class T> T div_floor(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>=0 ? a/b : (a+1)/b-1;
}
template<class T> T div_ceil(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>0 ? (a-1)/b+1 : a/b;
}

constexpr lint mod = 1e9+7;
constexpr lint INF = mod * mod;
constexpr int MAX = 200010;

int main(){
    string s;
    cin >> s;
    int n = s.size();
    int X[n+1];
    X[0] = 0;
    rep(i, n) X[i+1] = X[i] ^ (1 << (s[i]-'a'));

    int dp[n+1];
    fill(dp, dp+n+1, MAX);
    dp[0] = 0;
    map<int, int> mp;
    mp[0] = 0;
    For(i, 1, n+1){
        if(mp.find(X[i]) != mp.end()) dp[i] = mp[X[i]] + 1;
        rep(j, 26){
            int t = X[i] ^ 1<<j;
            if(mp.find(t) != mp.end()) chmin(dp[i], mp[t] + 1);
        }
        if(mp.find(X[i]) == mp.end()) mp[X[i]] = dp[i];
        else chmin(mp[X[i]], dp[i]);
    }
    printf("%d\n", dp[n]);
}

Measured memory_bytes: 11396
#include<stdio.h>
int main(){
  int n,a,b,i;
  long k,sum=0,t[100001];
  scanf("%d%ld",&n,&k);
  for(i=0; i<100001; i++){
    t[i]=0;
  }
  for(i=0; i<n; i++){
    scanf("%d%d",&a,&b);
    t[a]+=b;
  }
  for(i=1; i<100001; i++){
    sum=sum+t[i];
    if(sum>=k){
      printf("%d\n",i);
      break;
    }
  }
  return 0;


}

Measured memory_bytes: 896
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <iomanip>
#include <climits>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<string> VS;
typedef vector< vector<int> > VVI;
typedef vector< vector<ll> > VVL;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define pf push_front
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define ub upper_bound
#define lb lower_bound

int main(){
  int N;
  cin>>N;
  VL A(N);
  rep(i,N) cin>>A[i];
  VVL dp(N+2,VL(N%2+2));
  rep(i,N+2) rep(j,N%2+2) dp[i][j]=-1001001001001001;
  dp[0][0]=0;
  rep(i,N+1){
    rep(j,N%2+2){
      if(j<N%2+1) dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]);
      if(i<N) dp[i+2][j]=max(dp[i+2][j],dp[i][j]+A[i]);
    }
  }
  cout<<dp[N+1][N%2+1]<<endl;
}



Measured memory_bytes: 15608