akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define print(x)cout<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;

//dp[S][v]:= 頂点集合Sを訪れて現在位置がvのときの、後に通る最短経路長
ll dp[1<<16][16];
ll dist[16][16];
int n,e;
const ll INF = 100100100;

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

ll rec(int S, int v){
  if(dp[S][v] != -1) return dp[S][v];

  //全て訪れている場合
  if(S == (1<<n)-1 && v == 0){
    return dp[S][v] = 0;
  }

  ll res = INF;
  //頂点集合からvを抜く
  rep(u,n){
    if(!(S >> u & 1)){
    //最後にvを辿るとしたときに、コストが最小となる頂点uを探索
    mins(res,rec(S|1<<u,u)+dist[v][u]);
    }
  }

  return dp[S][v] = res;
}


int main() {
  //rep(i,n)rep(j,n)cin >> dist[i][j];
  cin >> n >> e;
  Fill(dp,-1);
  Fill(dist,INF);

  rep(i,e){
    int s,t,d;
    cin >> s >> t >> d;
    dist[s][t] = d;
  }
  ll res = INF;
  res = rec(0,0);
  if(res == INF)res = -1;
  print(res);
  return 0;
}


Measured memory_bytes: 11304
import java.util.Scanner;
import java.util.stream.*;
class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        System.out.println((IntStream.range(0,N).map(i -> scan.nextInt()).map(i -> i%2).sum()%2 == 0 ? "YES":"NO"));
    }
}

Measured memory_bytes: 51588
require "complex"

N, D = gets.chomp.split.map(&:to_i)
X = N.times.map { gets.chomp.split.map(&:to_f) }

m = Math.sqrt(400.0 ** 2 * 10.0).ceil

ans = 0
X.combination(2) { |y, z|
  sum = 0
  for i in 0..D - 1
    sum += (y[i] - z[i]) ** 2
  end

  #p Math.sqrt(sum)

  for n in 1..m
    if n ** 2 == sum
      ans += 1
      break
    end
  end
}

puts ans


Measured memory_bytes: 3836
#include <stdio.h>
int main(void)
{
	float a, b;
	int m1, m2, n, l = 0;
	scanf("%f %f", &a, &b);
	
	for(n = 0; n <= 1000; n++){
		m1 = n * 8 / 100;
		m2 = n / 10;
		if(m1 == a && m2 == b){
			printf("%d", n);
			l++;
			break;
		}
	}
	
	if(l == 0){
		printf("-1");
	}
	
	return 0;
}

Measured memory_bytes: 128
n, k = [int(i) for i in input().split()]
if k % 2 == 1:
    print((n//k)**3)
else:
    k = k//2
    if (n//k)%2 == 0:
        print(((n//k)//2)**3 *2)
    else:
        print(((n//k)//2+1)**3 + ((n//k)//2)**3)


Measured memory_bytes: 3060
#include <iostream>
#include <cassert>
#include <climits>
#include <bitset>
#include <stack>
#include <queue>
#include <iomanip>
#include <limits>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <tuple>
#include <time.h>
#include <random>

using namespace std;

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

long long int INF = 3e18;
double Pi = 3.1415926535897932384626;

vector<ll> G[500005];
vector<P> tree[500010];
priority_queue <ll> pql;
priority_queue <P> pqp;
//big priority queue
priority_queue <ll,vector<ll>,greater<ll> > pqls;
priority_queue <P,vector<P>,greater<P> > pqps;
//small priority queue
//top pop

int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,-1,1};
char dir[] = "DRUL";
//ll bit[500005];
//↓,→,↑,←


#define p(x) cout<<x<<endl;
#define el cout<<endl;
#define pe(x) cout<<(x)<<" ";
#define ps(x) cout<<fixed<<setprecision(25)<<x<<endl;
#define pu(x) cout<<(x);
#define pd(x) cerr<<"//"<<(x)<<endl;
#define re(i,n) for(i=0;i<n;i++);
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define deba(x) cout<< #x << " = " << x <<endl


ll mod = 1000000007;
ll rui(ll number1,ll number2){
    if(number2 == 0){
        return 1;
    }else{
        ll number3 = rui(number1,number2 / 2);
        number3 *= number3;
        number3 %= mod;
        if(number2%2==1){
            number3 *= number1;
            number3 %= mod;
        }
        return number3;
    }
}
ll gcd(ll number1,ll number2){
    if(number1 > number2){
        swap(number1,number2);
    }
    if(number1 == 0 || number1 == number2){
        return number2;
    }else{
        return gcd(number2 % number1,number1);
    }
}
void YES(bool condition){
    if(condition){
        p("YES");
    }else{
        p("NO");
    }
    return;
}
void Yes(bool condition){
    if(condition){
        p("Yes");
    }else{
        p("No");
    }
    return;
}

ll n,m,num,sum,ans,a,b,c,d,e,g,h,w,i,j,k,q,l,r;
ll x[500005],y[500005],z[1200005];
ll dp[1005][1005];
bool flag,dame;
ll sta;
ll po[1200000];
 
int main(){
	cin >> h >> w >> n;
	//2n * 2n の周期が繰り返される
	ll syuki = 2 * n;
	for(i=0;i<2*n;i++){
		for(j=0;j<2*n;j++){
			//回転後の盤面の座標によって塗る色を決める
			a = 0;
			if(0 <= (i + j) % syuki && ((i + j) % syuki) < n)a += 2;
			if(0 <= ((i - j + 1000 * syuki) % syuki) && ((i - j + 1000 * syuki) % syuki) < n)a += 1;
			dp[i][j] = a;
		}
	}
	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			//さっき決めた周期のテーブルを参照する
			a = i % syuki;
			b = j % syuki;
			if(dp[a][b] == 1)pu("R");
			if(dp[a][b] == 2)pu("Y");
			if(dp[a][b] == 3)pu("G");
			if(dp[a][b] == 0)pu("B");
		}
		el;
	}
	return 0;
}

Measured memory_bytes: 44032
#pragma region Macros
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using WGraph = vector<vector<pair<int, ll>>>;

template<class T>inline bool chmax(T &a, const T &b) { if (b > a) { a = b; return true; } return false; }
template<class T>inline bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

constexpr int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
constexpr int INF = 1e9;
constexpr long long LINF = 1e18;
constexpr long long MOD = 1e9 + 7;
constexpr double EPS = 1e-10;
constexpr double PI = M_PI;
#pragma endregion

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> dp(3, vector<int>(n+1));
    for (int i=0; i<n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        dp.at(0).at(i+1) = max(dp.at(1).at(i), dp.at(2).at(i)) + a;
        dp.at(1).at(i+1) = max(dp.at(2).at(i), dp.at(0).at(i)) + b;
        dp.at(2).at(i+1) = max(dp.at(0).at(i), dp.at(1).at(i)) + c;
    }
    int res = 0;
    for (int i=0; i<3; i++) chmax(res, dp.at(i).back());
    cout << res << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    solve();

    return 0;
}


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

int n, A[6003], B[6003];
int id[6003], nx[6003];
string s, res[6003];

int main() {
    cin >> n >> s, s = " " + s;
    for (int i = 1, ca = 0, cb = 0; i <= n * 2; ++i)
        (s[i] ^ 'a') ? B[id[i] = ++cb] = i : A[id[i] = ++ca] = i;
    A[n + 1] = B[n + 1] = n * 2 + 1;

    for (int i = 1, p = 1; i <= n + 1; ++i)
        while (p < min(A[i], B[i])) nx[p++] = i;

    for (int i = n, p, mx; i >= 1; --i) {
        if (B[i] < A[i]) {
            for (p = B[i], mx = A[i]; p <= mx; ++p)
                if (id[p] >= i) res[i] += s[p], mx = max(mx, A[id[p]]);
            res[i] += res[id[p]];
        } else {
            res[i] = "ab" + res[nx[B[i]]];
        }
        res[i] = max(res[i], res[i + 1]);
    }
    cout << res[1] << endl;
    return 0;
}


Measured memory_bytes: 16504
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  int H[N];
  for (int i=0;i<N;i++){
    cin >> H[i];
  }
  bool ans=true;
  for (int i=1;i<N;i++){
    if (H[i-1]==H[i]){
      continue;
    }
    if (H[i-1]<H[i]){
      H[i]--;
    }
    else {
      ans=false;
      break;
    }
  }
  if (ans){
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <set>
#include <map>
using namespace std;

#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define REPI(i, s, e) for (int i = (s); i <= (e); i++)
#define rep(i, n) REP(i, 0, n)
#define repi(i, n) REPI(i, 0, n)
#define ALL(v) (v).begin(), (v).end()

#define dump(x) (cout << #x << " = " << x << endl)
#define dump2(x, y) (cout << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")" << endl)

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

int main(void)
{
	string ms[] = { "",
					".,!? ",
                    "abc",
					"def",
					"ghi",
					"jkl",
					"mno",
					"pqrs",
					"tuv",
					"wxyz" };

	int n;
	cin >> n;
	rep(TTT, n) {
		string str;
		cin >> str;
		vector<pii> ks;
		int prev = 0;
		int cnt = 0;
		rep(k, str.size()) {
			int i = str[k]-'0';
			if (prev != i) {
				if (prev != 0)
					putchar(ms[prev][cnt]);
				prev = i;
				cnt = 0;
			} else {
				if (prev != 0)
					cnt = (cnt+1)%ms[prev].size();
			}
		}
		if (prev != 0)
			putchar(ms[prev][cnt]);
		putchar('\n');
	}
	return 0;
}

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

int arr[26];
int main()
{
    string h;
    cin >> h;
    set<char> s;
    for (int i = 0; i < h.length(); i++)
    {
        s.insert(h[i]);
        arr[h[i] - 'A']++;
    }
    vector<char> v(s.begin(), s.end());
    if (s.size() == 2)
    {
        for (int i = 0; i < v.size(); i++)
        {
            if (arr[v[i] - 'A'] == 2)
                continue;
            else
                return cout << "No", 0;
        }
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

int main() {
    int N; cin >> N;
    vector<int> A(N);
    for (int &x : A) cin >> x;
    ll ans = 0, cnt = 0;
    int pt = 0;
    while (pt < N) {
        while (pt < N && A[pt] != 0) cnt += A[pt++];
        ans += cnt / 2;
        cnt = 0;
        pt++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
x, y, arg = 0, 0, 90 * Math::PI / 180

while line = gets do
  r, deg = line.split(",").map(&:to_i)
  x += r * Math.cos(arg)
  y += r * Math.sin(arg)
  arg -= deg * Math::PI / 180
  #p x, y
end

puts x.to_i, y.to_i

Measured memory_bytes: 6160
// Wide Flip
#include <bits/stdc++.h>
using namespace std;
string s;
int n;
int main(){
    cin>>s;
    n=s.size();
    int ans=n/2;
    char c=s[ans];
    while(s[ans]==s[n-ans-1]&&s[ans]==c)ans++;
    cout<<ans<<endl;
}

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

int main() {
  int n, m;
  cin >> n >> m;
  set<int> ans_or;
  map<int, int> mp;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    mp[a] += 1;
    ans_or.insert(a);
  }
  set<int> ans_and;
  for (int i = 0; i < m; i++) {
    int b;
    cin >> b;
    if (mp.find(b) != mp.end()) ans_and.insert(b);
    ans_or.insert(b);
  }
  cout << ans_and.size() << ' ' << ans_or.size() << endl;
  for (auto x : ans_and) {
    cout << x << endl;
  }
  for (auto x : ans_or) {
    cout << x << endl;
  }
}



Measured memory_bytes: 20116
#include <iostream>
using namespace std;
using ll=long long;

int main(){
  ll W,H,x,y;cin>>W>>H>>x>>y;
  double s = (W*H)/2.0;
  int dup = 0;
  if (x*2==W && y*2==H) dup = 1;
  printf("%lf %d\n", s, dup);
}



Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int a[n+5];
	int m[n+5];
	for(int i=1;i<=n;i++)
		cin>>a[i];
	m[1]=a[1]*2;
	for(int i=2;i<=n;i++)
		m[i]=(a[i-1]*2)-m[i-1];
	int x=0;
	while(a[n]*2!=m[1]+m[n])
	{
		x+=2;
		m[1]-=2;
		m[n]-=2;
	}
	cout<<m[1]<<" ";
	for(int i=2;i<n;i++)
	{
		if(i%2==0) m[i]+=x;
		else m[i]-=x;
		cout<<m[i]<<" ";
	}
	cout<<m[n]<<" ";
	return 0;
}

Measured memory_bytes: 2048
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<string>
#include<vector>
#include<math.h>
#include<queue>
#include<stdlib.h>
#include<ctype.h>
#include<limits.h>
#include<map>
#include<limits.h>
#include<ctype.h>
#include<set>
#define pb push_back
#define all(v) v.begin(),v.end()
#define sz size()
#define fast ios_base::sync_with_stdio(false);
#define pq priority_queue
#define mp make_pair
#define mod 1000000007
#define inf 1000000000000000000
using namespace std;
typedef long long ll;
vector<ll> vv[2005];
ll depth[2005];
void dfs(ll v,ll p,ll d)
{
	depth[v]=d;
	ll i;
	for(i=0;i<vv[v].size();i++)
	{
		ll k=vv[v][i];
		if(k==p)
		continue;
		else
		dfs(k,v,d+1);
	}
}
ll a[2005],b[2005];
int main()
{
	ll n,k;
	cin>>n>>k;
	ll ans=10000000000000;
	for(ll i=1;i<=n-1;i++)
	{
		cin>>a[i]>>b[i];
		vv[a[i]].push_back(b[i]);
		vv[b[i]].push_back(a[i]);
	}
	if(k%2==0)
	{
		for(ll i=1;i<=n;i++)
		{
			ll count=0;
			dfs(i,-1,0);
			for(ll j=1;j<=n;j++)
			{
				if(depth[j]>k/2)
				count++;
			}
			ans=min(ans,count);
		}
	}
	else
    {
    	for(ll i=1;i<=n-1;i++)
    	{
    	   dfs(a[i],b[i],0);
    	   dfs(b[i],a[i],0);
    	   ll count=0;
    	   for(ll j=1;j<=n;j++)
    	   if(depth[j]>(k-1)/2)
    	   count++;
    	   ans=min(ans,count);
		}
	}
	cout<<ans<<endl;
	return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxd = 63, mod = 1000000007;
ll dp[maxd][32], l, r;
int dl[maxd], dr[maxd], x;

int main()
{
	cin >> l >> r;
	for (int i = 0; i < maxd; i++)
	{
		dl[i] = l & 1;
		dr[i] = r & 1;
		l >>= 1;
		r >>= 1;
	}
	for (int i = 1; i < 32; i += 2)
		dp[0][i] = 1;
	for (int i = 1; i < maxd; i++)
	{
		for (int j = 0; j < 32; j++)
		{
			if (dl[i - 1] == 0 || ((j & 4) && (j & 16)))
			{
				x = 0;
				if (0 < dr[i - 1])
					x = 10;
				dp[i][j] += dp[i - 1][j | x];
				dp[i][j] %= mod;
			}
			if (dr[i - 1] == 1 || ((j & 2) && (j & 8)))
			{
				x = 1;
				if (1 > dl[i - 1])
					x = 21;
				dp[i][j] += dp[i - 1][j | x];
				dp[i][j] %= mod;
			}
			if ((j & 1) && (dl[i - 1] == 0 || (j & 16)) && (dr[i - 1] == 1 || (j & 2)))
			{
				x = 0;
				if (0 < dr[i - 1])
					x |= 8;
				if (1 > dl[i - 1])
					x |= 4;
				dp[i][j] += dp[i - 1][j | x];
				dp[i][j] %= mod;
			}
		}
	}
	cout << dp[maxd - 1][0];
	return 0;
}


Measured memory_bytes: 256
n,weight=map(int,input().split())
v=[0]*n
w=[0]*n
for i in range(n):
    v[i],w[i]=map(int,input().split())
    
dp=[[0]*(weight+1) for i in range(n+1)]

for i in range(n):
    for j in range(weight+1):
        if j-w[i]>=0:
            dp[i+1][j]=max(dp[i][j-w[i]]+v[i],dp[i][j])
        else:
            dp[i+1][j]=dp[i][j]
print(dp[-1][-1])



Measured memory_bytes: 41888
#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("YES")
#define p_no() p("NO")

template < typename T >
void vprint(T &V){
	for(auto v : V){
    	cout << v << " ";
	}
	cout << endl;
}

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

const ll mod = 1e9 + 7;
const ll inf = 1e18;

vector<ll> A;
ll K;

ll f(ll X, ll p){
    return X - X % p;
}

ll g(ll X){
    FOR(i, 0, K){
        X = f(X, A[i]);
    }
    return X;
}

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

    // input
    cin >> K;
    A.resize(K);

    FOR(i, 0, K){
        cin >> A.at(i);
    }

    // 2より小、2の境界を探す
    ll left = 1;
    ll right=  inf;
    while(left + 1 != right){
        ll center = (left + right) / 2;
        if(g(center) < 2){
            left = center;
        }else{
            right = center;
        }
    }

    ll answer0 = right;

    // 2, 2より大の境界を探す
    left = 1;
    right = inf;
    while(left + 1 != right){
        ll center = (left + right) / 2;
        if(g(center) > 2){
            right = center;
        }else{
            left = center;
        }
    }

    ll answer1 = left;
    
    if(answer0 > answer1){
        p(-1);
    }else{
        p2(answer0, answer1);
    }

    return 0;
}

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

int main() {
  int a,b,c;cin>>a>>b>>c;
  cout << a+b+c-max(max(a,b),c);
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007;
// const int MOD = 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
const int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
  IOSetup() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  }
} iosetup;

int main() {
  int n; cin >> n;
  vector<int> a(n); REP(i, n) cin >> a[i];
  int ans = 0;
  REP(i, n) ans += i % 2 == 0 && a[i] % 2 == 1;
  cout << ans << '\n';
  return 0;
}


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

    int main(void){
    	ll n,m;
    	cin>>n>>m;
    	ll a[n];
    	for(int i=0;i<n;i++)cin>>a[i];
    	ll b[m],c[m];
    	vector<pair<ll,ll>>ans;
    	for(int i=0;i<m;i++){
    		cin>>b[i]>>c[i];
    		ans.push_back(make_pair(c[i],b[i]));
    	}
    	for(int i=0;i<n;i++){
    		ans.push_back(make_pair(a[i],1LL));
    	}
    	sort(ans.begin(),ans.end(),greater<pair<ll,ll>>());
    	ll res =0;
      ll num = n;
    	for(ll i=0;i<m+num+11;i++){
    		res += ans[i].first * ans[i].second;
    		n -= ans[i].second;
    		if(n==0){
    			break;
    		}else if(n<0){
    			res+=ans[i].first*n;
    			break;
    		}
    	}


    	cout<<res<<endl;
    }


Measured memory_bytes: 8816
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
 
using namespace std;
int R,C,N;
 
int length(int x,int y){
    if(y==0){
        return x;
    }
    if(x==0){
        return 2*(R+C)-y;
    }
    if(x==R){
        return R+y;
    }
    return 2*R+C-x;
}
 
bool comp(pair<int,int>& p1,pair<int,int>& p2){
    return p1.first - p2.first;
}
 
int main() {
    cin>>R>>C>>N;
    vector<pair<int,int>> border;
 
    REP(i,N){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        if ((x1%R==0||y1%C==0)&&(x2%R==0||y2%C==0)){
            border.push_back(pair<int,int>(length(x1,y1),i+1));//   [length(x1,y1)]=i+1;
            border.push_back(pair<int,int>(length(x2,y2),i+1));
        }
    }
    sort(border.begin(),border.end());
 
    stack<int> pos;
    pos.push(-1);
 
    REP(i,border.size()) {
        if(pos.top()!=border[i].second){
                pos.push(border[i].second);
            }else{
                pos.pop();
            }
    }
 
    if(pos.size()==1){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
    return 0;
}

Measured memory_bytes: 2420
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
#include <numeric>
#include <string>
#include <functional>
 
using namespace std;
 
int main() {
  int a,b,t;
  cin >> a >> b >> t;
  
  int pre = (t+0.5)/a;
  int ans = pre * b;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int cnt=0;
  string s;
  cin>>s;
  for(int i=0;i<s.length();i++)
  {   
     if(i%2!=0)
     {
       if(s[i]=='L' || s[i]=='U'|| s[i]=='D')
       {
         cnt++;
       }
     }
    else
    {
      if(s[i]=='R' || s[i]=='U'|| s[i]=='D')
       {
         cnt++;
       }
    }  
  }
 if(cnt==s.length())
 {
   cout<<"Yes";
 }
 else
 {
   cout<<"No";
 }
   return 0;
}

Measured memory_bytes: 256
import std.stdio, std.math, std.algorithm, std.array, std.string, std.conv, std.container, std.range;
T Read(T)() { return readln.chomp.to!(T); }
T[] Reads(T)() { return readln.split.to!(T[]); }
alias read = Read!(int);
alias reads = Reads!(int);


void main() {
    int n, k;
    readf("%d %d\n", &n, &k);
    int[] h = reads();

    auto dp = new long[n];
    dp[] = long.max;
    dp[0] = 0;
    foreach (i; 1..n) {
        foreach (j; 1 .. k+1) {
            int dst = i - j;
            if (dst < 0) break;
            dp[i] = min(dp[i],
                    abs(h[i] - h[dst]) + dp[dst]);
        }
    }
    writeln(dp[n - 1]);
}


Measured memory_bytes: 4380
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N,i=1;
  cin>>N;
  for(;true;i++){
    if(i*(i+1)/2>=N)
      break;
  }
  for(;i>0;i--){
    if(N>=i){
      cout<<i<<endl;
      N-=i;
    }
    if(N==0)
      break;
  }
}

Measured memory_bytes: 3636
package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

func main() { 
    var input []string
    
    sc := bufio.NewScanner(os.Stdin)
    for sc.Scan() {
        input = append(input, sc.Text())
    }
    
    X, _ := strconv.Atoi(input[0])
    A, _ := strconv.Atoi(input[1])
    B, _ := strconv.Atoi(input[2])                                                                 

    fmt.Println((X - A) % B)
}

Measured memory_bytes: 640
#include <stdio.h>

void judge(int pm, int pe, int pj);

int main(void)
{
    int dataset;
    int pm, pe, pj;

    while (1){
        scanf("%d", &dataset);
        if (dataset == 0){
            break;
        } else {
            while (dataset--){
                scanf("%d %d %d", &pm, &pe, &pj);
                judge(pm, pe, pj);
            }
        }
    }

    return 0;
}

void judge(int pm, int pe, int pj)
{
    if (pm == 100 || pe == 100 || pj == 100){
        printf("A\n");
    } else if (pm + pe >= 90 * 2){
        printf("A\n");
    } else if (pm + pe + pj >= 80 * 3){
        printf("A\n");
    } else if (pm + pe + pj >= 70 * 3){
        printf("B\n");
    } else if (pm + pe + pj >= 50 * 3 && (pm >= 80 || pe >= 80)){
        printf("B\n");
    } else {
        printf("C\n");
    }
}

Measured memory_bytes: 1008
#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
#include <queue>
#include <map>
#include <cmath>
#include <numeric>
#include <tuple>

using namespace std;

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

const long long mod = 1e9 + 7;

int main() {
    
    ll n;
    cin >> n;
    vector<ll> p(n);
    map<ll, P> mr;
    map<ll, P> ml;
    for (int i = 0; i < n; ++i)
    {
        cin >> p[i];
        mr[p[i]] = P(i, p[i]);
    }
    vector<ll> pr = p;
    reverse(pr.begin(), pr.end());
    
    for (int i = 0; i < n; ++i)
    {
        ml[pr[i]] = P(i, pr[i]);
    }
    
    vector<ll> l1(n);
    vector<ll> l2(n);
    vector<ll> r1(n);
    vector<ll> r2(n);
    
    set<P> l;
    set<P> r;
    l.insert(P(n, n + 1));
    r.insert(P(n, n + 1));
    for (int i = n; i >= 1; --i)
    {
        auto itr1 = r.lower_bound(mr[i]);
        auto itr2 = r.upper_bound(*itr1);
        if (itr2 == r.end())
        {
            itr2--;
        }

        r1[mr[i].first] = itr1->first - mr[i].first;
        r2[mr[i].first] = itr2->first - itr1->first;
        r.insert(mr[i]);
    }
    
    for (int i = n; i >= 1; --i)
    {
        auto itr1 = l.lower_bound(ml[i]);
        auto itr2 = l.upper_bound(*itr1);
        if (itr2 == l.end())
        {
            itr2--;
        }
        
        l1[n - 1 - ml[i].first] = itr1->first - ml[i].first;
        l2[n - 1 - ml[i].first] = itr2->first - itr1->first;
        l.insert(ml[i]);
    }
    
    ll ret = 0;
    for (int i = 0; i < n; ++i)
    {
        ret += l1[i] * r2[i] * p[i];
        ret += l2[i] * r1[i] * p[i];
    }
    cout << ret << endl;
    
    return 0;
}


Measured memory_bytes: 29952
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
using namespace std;
const int MAXN = (int)1e4 + 10;
const int INF = (int) 0x3f3f3f3f;

static int read(int& x){
    char c=getchar();
    x=0;
    while(c<'0'||c>'9') c=getchar();
    while('0'<=c&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
}

vector<int> g[MAXN],val[MAXN];
int n;
int d[MAXN],vis[MAXN];

void SPFA(){
    queue<int> q;
    for(int i=1;i<=n;i++) d[i]=INF;
    d[0]=0;
    q.push(0);
    vis[0]=1;
    while(!q.empty()){
        int u=q.front(); q.pop();
        vis[u]=0;
        for(int i=0;i<g[u].size();i++){
            int v=g[u][i];
            if(d[v]>d[u]+val[u][i]){
                d[v]=d[u]+val[u][i];
                if(!vis[v]){
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
}

void work(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int u,k; read(u); read(k);
        while(k--){
            int v,c;
            read(v); read(c);
            g[u].push_back(v);
            val[u].push_back(c);
        }
    }
    SPFA();
    for(int i=0;i<n;i++) printf("%d %d\n",i,d[i]);
}

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

/*
5
0 3 2 3 3 1 1 2
1 2 0 2 3 4
2 3 0 3 3 1 4 1
3 4 2 1 0 1 1 4 4 3
4 2 2 1 3 3
*/



Measured memory_bytes: 7812
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional> // for less 
using namespace __gnu_pbds; 
#define mod 998244353 
#define int long long
#define ll long long
#define pb push_back
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define inp(n) for(i=0;i<n;i++) cin>>A[i];
#define inz(A) memset(A,0,sizeof(A))
#define lb lower_bound
#define ub upper_bound
#define all(v) v.begin(),v.end()
#define T 1000005
#define F first
#define S second
#define pi pair<int,int>
#define vi vector<int>
#define mii map<int,int>
#define vp vector<pair< int,int> >
#define mpi map<pair<int,int> ,int>
#define PI M_PI
#define lower(s) transform(all(s),s.begin(),::tolower)
#define endl "\n"
typedef tree<int, null_type, less<int>, rb_tree_tag, 
         tree_order_statistics_node_update> pbds;
int add(int a, int b) {a=(a%mod + b%mod)%mod;return a;}
int sub(int a, int b) {a =(a%mod - b%mod + mod)%mod ;return a;}
int mul(int a, int b) {return (a%mod * b%mod) % mod;}


void solve()
{  
   int n,m,k,a=0,b=0;cin>>n>>m>>k;
   char c[n][m];
   for(int i=0;i<n;i++)
   for(int j=0;j<m;j++)
   {
       cin >> c[i][j];
       if(c[i][j]=='.')a++;
       else b++;
   }

    int ans=0;
   for(int i=0;i<(1<<n);i++)
   {
       for(int j=0;j<(1<<m);j++)
       {    int cnt=0;
           for(int i1=0;i1<n;i1++)
           {
               for(int j1=0;j1<m;j1++)
               {    
                   int f=pow(2,i1);
                   int f1=pow(2,j1);
                   if( (i&f)==0 && (j&f1)==0 && c[i1][j1]=='#')
                   cnt++;
               }
           }
           if(cnt==k)ans++;
       }
   }
   cout << ans;
}

signed main()
{ 
    boost
    int test=0,t;
    //cin >> t ;
    t=1;
   while(test++ <t){
	  //cout<<"Case #"<<test<<": ";
	   solve();}
  
}

Measured memory_bytes: 4048
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 500 + 5

int n, R[N];
double ans, Pos[N];

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++)
		scanf("%d", R + i);
	for (int i = 1; i <= n; i ++)
	{
		double Max = 1.0 * R[i];
		for (int j = 1; j < i; j ++)
		{
			double x = Pos[j] + 2 * sqrt(1.0 * R[i] * R[j]);
			Max = max(Max, x);
		}
		Pos[i] = Max;
		ans = max(ans, Pos[i] + 1.0 * R[i]);
	}
	printf("%.6lf\n", ans);
	return 0;
}

Measured memory_bytes: 1068
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n,m;cin>>n>>m;
  vector<int>a(n);
  ll sum=0;
  for(ll i=0;i<n;++i){
    cin>>a[i];
    sum+=a[i];
  }
  if(n-sum>=0){
    cout<<n-sum<<endl;
  }else{
    cout<<"-1"<<endl;
  }
}

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

int main(){
  int N;
  string S;
  cin>>N;
  cin>>S;
  for(int i=0;i<S.size();i++){
    if(S[i]+N>'Z')S[i]-=(26-N);
    else S[i]+=N;
  }
  cout<<S<<endl;
  return 0;
}

Measured memory_bytes: 256
#!/usr/bin/python3

import sys

def dprint(*args):
    return
    print(*args)

def solve(s_str):
    ans = 0
    s_len = len(s_str)
    for bits in range(0, 1 << (s_len - 1)):
        dprint("bits: {0:b}".format(bits))
        rev_str = list(reversed(s_str))
        #dprint(f"rev_str: {rev_str}")
        cur_num_rev_str = ""
        # 12345
        for rev_i in range(0, s_len):
            dprint("rev_i: %d" % rev_i)
            plus_index = rev_i
            cur_num_rev_str += rev_str[0]
            rev_str = rev_str[1:]
            dprint("cur_num_rev_str: %s" % cur_num_rev_str)
            if rev_i == s_len - 1 or bits & (1 << plus_index):
                ans += int(''.join(list(reversed(cur_num_rev_str))))
                cur_num_rev_str = ""
    return ans

def main():
    s_str = sys.stdin.read().rstrip()
    dprint(s_str)
    print(solve(s_str))

main()

Measured memory_bytes: 3064
#include <algorithm>
#include <array>
#include <bitset>
#include <complex>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using namespace std;

struct BoolName : numpunct<char> {
  string t, f;
  BoolName (string t = "Yes", string f = "No") : t(t), f(f) {}
  string do_truename() const {return t;}
  string do_falsename() const {return f;}
};

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15) << boolalpha;
    cout.imbue(locale(cout.getloc(), new BoolName));
  }
} initializer;

template<typename T> istream& operator>>(istream &s, vector<T> &v) {
  for (T &t : v) s >> t;
  return s;
}

template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
  for (const T &t : v) s << t << endl;
  return s;
}

void set_bool_name(string t, string f) {
  cout.imbue(locale(cout.getloc(), new BoolName(t, f)));
}

template<typename T> bool chmin(T& a, T b) {return a > b ? a = b, true : false;}

template<typename T> bool chmax(T& a, T b) {return a < b ? a = b, true : false;}

int main() {
  int n, k;
  cin >> n >> k;
  vector<int64_t> x(n);
  cin >> x;
  int64_t res = numeric_limits<int64_t>::max();
  for (int i = 0; i + k <= n; ++i) {
    if (x[i] > 0) {
      chmin(res, x[i + k - 1]);
    } else if (x[i + k - 1] < 0) {
      chmin(res, -x[i]);
    } else {
      chmin(res, 2 * abs(x[i]) + abs(x[i + k - 1]));
      chmin(res, abs(x[i]) + 2 * abs(x[i + k - 1]));
    }
  }
  cout << res << endl;
}



Measured memory_bytes: 1152
A = int(input())
B = int(input())
C = int(input())
x = int(input())
ans = 0
for a in range(A+1):
    for b in range(B+1):
        for c in range(C+1):
            if a*500 + b*100 + c*50 == x:
                ans += 1 
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <algorithm>
#include <queue>
using namespace std;
int main(){
	int N; 
	cin >> N; 
	long long int first = 1, second = 1; 
	for(int i = 0; i < N; i++){
		long long int T, A; 
		cin >> T >> A; 
		long long int K = max((first + T - 1)/ T, (second + A - 1)/ A);  
		first = K * T, second = K * A; 
	}
	cout << first + second << endl;
}

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

int main() {

    int n;
    string s;
    cin >> n >> s;
    int marubatsu;
    marubatsu = 0;

    for(int i = 0; i < n; i++){
        if(s[i] == 'O'){
            if(s[i + 1] == 'X'){
                marubatsu++;
                i++;
            }
        }
        else if(s[i] == 'X'){
            if(s[i + 1] == 'O'){
                marubatsu++;
                i++;
            }
        }
    }
    cout << marubatsu << endl;

}




Measured memory_bytes: 3348
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <iomanip>
# define M_PIl        3.141592653589793238462643383279502884
#define faster       ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

typedef long long ll;
typedef long double ld;

map<ll,ll> m;

bool check(int t){
  if(t!=1){
    if(m[1]){
      return false;
    }
    if((m[t])>1){
      return false;
    }
  }
  else{
    if(m[1]>1){
      return false;
    }
  }
  for(int i=2;i<=sqrt(t);i++){
    if(t%i==0){
      if((m[t/i])||(m[i])){
        return false;
      }
    }
  }
  return true;
}

int main(){
  faster;
  int n;
  cin >> n;
  vector<int> arr(n);
  for(int i=0;i<n;i++){
    int a;
    cin >> a;
    arr[i]=a;
    m[a]++;
  }
  int ans=0;
  for(int i=0;i<n;i++){
    if(check(arr[i])){
      ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 42100
#include <iostream>
#include<string>
#include<algorithm>
#include <bits/stdc++.h>
#define ll long long  
using namespace std;
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s,t;
  cin>>s>>t;
  int count=0;
  for(int i=0;i<3;i++){
    if(s[i]==t[i]) count++;  
    }
    
    cout<<count<<endl;
  
  
  
  return 0;
}


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

using namespace std;


//repetition
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define euc_dis(x, y) sqrt(x*x + y*y)

#define MOD 1e9+7
#define sp ' '


using ll = long long;


ll mod(ll a, ll b){return (a%b+b)%b;}
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void Judge(bool b){b?Yes():No();}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void JUDGE(bool b){b?YES():NO();}
ll powMod(ll b, ll e, ll m){ll r=1;while(e>0){if(e&1)r=(r%m)*(b%m)%m;b=(b%m)*(b%m)%m;e>>=1;}return r;}
double distance(ll x1, ll y1, ll x2, ll y2){return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));}

template<typename T>
void ppp(T n){cout << n << endl;}

int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;

    int a[n];
    rep(i, n){
        cin >> a[i];
    }

    ll s[n+1];
    s[0] = 0;
    rep(i, n){
        s[i+1] = s[i] + a[i];
    }

    ll ans1 = 0, ans2 = 0, diff1 = 0, diff2 = 0;
    for(int i = 1; i <= n; ++i){
        if(i%2){
            if(s[i]+diff1 <= 0) {
                ll tmp = abs((s[i]+diff1)-1);
                ans1 += tmp;
                diff1 += tmp;
            }
            if(s[i]+diff2 >= 0) {
                ll tmp = abs((s[i]+diff2)+1);
                ans2 += tmp;
                diff2 -= tmp;
            }
        }
        else{
            if(s[i]+diff1 >= 0) {
                ll tmp = abs((s[i]+diff1)+1);
                ans1 += tmp;
                diff1 -= tmp;
            }
            if(s[i]+diff2 <= 0) {
                ll tmp = abs((s[i]+diff2)-1);
                ans2 += tmp;
                diff2 += tmp;
            }
        }
    }

    ppp(min(ans1, ans2));
    return 0;
}


Measured memory_bytes: 1408
#include<iostream>
#include<string>
int main(){
    std::string c;
    std::cin >> c;
    if(c=="a"){
        std::cout << "vowel" << std::endl;
    }
    else if(c=="e"){
        std::cout << "vowel" << std::endl;
    }
    else if(c=="i"){
        std::cout << "vowel" << std::endl;
    }
    else if(c=="o"){
        std::cout << "vowel" << std::endl;
    }
    else if(c=="u"){
        std::cout << "vowel" << std::endl;
    }
    else{
        std::cout << "consonant" << std::endl;
    }
    
    return 0;
}

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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const ll MOD = 1e9 + 7;

const int MAXN = 1e2 + 5;

vi g[MAXN];

int used1[MAXN];
int prv1[MAXN];
int dis1[MAXN];

void dfs1(int s){
	used1[s] = 1;
	REP(i, 0, SZ(g[s])){
		int to = g[s][i];
		if (!used1[to]){
			prv1[to] = s;
			dis1[to] = dis1[s] + 1;
			dfs1(to);
		}
	}
}

/*int used3[MAXN];
int dis3[MAXN];
int mx_dis3[MAXN];

void dfs3(int s){
	used3[s] = 1;
	mx_dis3[s] = dis3[s];
	REP(i, 0, SZ(g[s])){
		int to = g[s][i];
		if (!used3[to]){
			dis3[to] = dis3[s] + 1;
			dfs3(to);
			mx_dis3[s] = max(mx_dis3[s], mx_dis3[to]);
		}
	}
}*/

ll ans;

int used2[MAXN];

int cnt = 0;

void dfs2(vi vv, ll cur_cnt){
	
	
	/*cnt++;
	if (cnt > 1000){
		exit(1);
	}
	
	REP(i, 0, SZ(vv)){
		printf("%d ", vv[i]);
	}
	putchar('\n');*/
	
	REP(i, 0, SZ(vv)){
		used2[vv[i]] = 1;
	}
	vi nxts;
	int mx = 0;
	REP(i, 0, SZ(vv)){
		int s = vv[i];
		int cur = 0;
		REP(j, 0, SZ(g[s])){
			int to = g[s][j];
			if (!used2[to]){
				cur++;
				nxts.pb(to);
			}
		}
		mx = max(mx, cur);
	}
	if (nxts.empty()){
		if (ans == 0 || ans > cur_cnt){
			ans = cur_cnt;
		}
	} else {
		dfs2(nxts, cur_cnt * mx);
	}
}

vector<vi> centers;

void solve(){
	int n;
	scanf("%d", &n);
	REP(i, 1, n){
		int a, b;
		scanf("%d%d", &a, &b);
		g[a].pb(b);
		g[b].pb(a);
	}
	dfs1(1);
	int maxi1 = 1;
	REPN(i, 1, n){
		if (dis1[i] > dis1[maxi1]){
			maxi1 = i;
		}
	}
	REPN(i, 1, n){
		prv1[i] = 0;
		used1[i] = 0;
		dis1[i] = 0;
	}
	dfs1(maxi1);
	int maxi2 = 1;
	REPN(i, 1, n){
		if (dis1[i] > dis1[maxi2]){
			maxi2 = i;
		}
	}
	
	/*printf("%d %d\n", maxi1, maxi2);
	return;*/
	
	vi tmp;
	for(; maxi2 != maxi1; maxi2 = prv1[maxi2]){
		tmp.pb(maxi2);
	}
	tmp.pb(maxi1);
	
	int diam = SZ(tmp);
	if (diam % 2 == 0){
		vi roots;
		roots.pb(tmp[diam / 2 - 1]);
		roots.pb(tmp[diam / 2]);
		centers.pb(roots);
	} else {
		vi roots;
		roots.pb(tmp[diam / 2]);
		centers.pb(roots);
		
		int s = roots[0];
		roots.pb(0);
		REP(i, 0, SZ(g[s])){
			int to = g[s][i];
			roots[1] = to;
			centers.pb(roots);
		}
	}	
	
	REP(i, 0, SZ(centers)){
		REPN(j, 1, n){
			used2[j] = 0;
		}
		vi roots = centers[i];
		dfs2(roots, SZ(roots));
	}
	
	
	printf("%d %lld\n", (diam + 1) / 2, ans);
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


Measured memory_bytes: 256
//2018年  3月 21日 水曜日 23:32:19 JST
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cout << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cout<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 200010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 29;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
///////////////////////////////////////////////////////////////////////////////////////////////////

int N, T;
int A[MAX_N], B[MAX_N];

void solve() {
	cin >> N >> T;
	rep(i, 0, N) {
		cin >> A[i];
		B[i] = A[i];
	}
	rer(i, N - 1, 0) MAX(B[i], B[i + 1]);
	int diff = -1;
	rep(i, 0, N - 1) {
		MAX(diff, B[i + 1] - A[i]);
	}
	int res = 0;
	rep(i, 0, N - 1) {
		if(diff == B[i + 1] - A[i]) res++;
	}
	cout << res << "\n";
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
	srand((unsigned int)time(NULL));
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
    freopen("in.txt", "rt", stdin);
#endif	
	solve();
#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}



Measured memory_bytes: 1024
import queue

N, K = map(int, input().split())
p = list(map(int, input().split()))

for i in range(len(p)):
    p[i] = p[i] + 1

queue = queue.Queue()
currentSum = 0
maxSum = 0
for i in range(len(p)):
    currentSum = currentSum + p[i]
    queue.put(p[i])
    if i >= K:
        currentSum = currentSum - queue.get()

    if i >= K - 1:
        maxSum = max(maxSum, currentSum)

print("{:.12f}".format(maxSum / 2))


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

const int N=2e5+100;
const int mod=1e9+7;
typedef long long ll;


typedef pair<int,int> pa;

int n,m;

struct node
{
    ll x,y,z;

}a[2000];

bool cmp1(node x,node y)
{
     return x.x+x.y+x.z>y.x+y.y+y.z;
}

bool cmp2(node x,node y)
{
     return x.y+x.z-x.x>+y.y+y.z-y.x;
}

bool cmp3(node x,node y)
{
     return x.x-x.y+x.z>y.x-y.y+y.z;
}

bool cmp4(node x,node y)
{
     return x.x+x.y-x.z>y.x+y.y-y.z;
}

bool cmp5(node x,node y)
{
     return -x.x-x.y+x.z>-y.x-y.y+y.z;
}

bool cmp6(node x,node y)
{
     return -x.x+x.y-x.z>-y.x+y.y-y.z;
}

bool cmp7(node x,node y)
{
     return x.x-x.y-x.z>y.x-y.y-y.z;
}

bool cmp8(node x,node y)
{
     return -x.x-x.y-x.z>-y.x-y.y-y.z;
}
ll ans=0;

int dv[8][3]={{1,1,1},{-1,1,1},{1,-1,1},{1,1,-1},{-1,-1,1},{-1,1,-1},{1,-1,-1},{-1,-1,-1}};
void check(int q,int w,int e)
{
   ll sum=0;
   for(int i=1;i<=m;i++){
    sum+=q*a[i].x+w*a[i].y+e*a[i].z;
    }

    ans=max(ans,abs(sum));
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;

    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y>>a[i].z;
    }
    int t=0;
    sort(a+1,a+n+1,cmp1);
    check(dv[t][0],dv[t][1],dv[t][2]);
    t++;
    sort(a+1,a+n+1,cmp2);
    check(dv[t][0],dv[t][1],dv[t][2]);
    t++;
    sort(a+1,a+n+1,cmp3);
    check(dv[t][0],dv[t][1],dv[t][2]);
    t++;
    sort(a+1,a+n+1,cmp4);
    check(dv[t][0],dv[t][1],dv[t][2]);
    t++;
    sort(a+1,a+n+1,cmp5);
    check(dv[t][0],dv[t][1],dv[t][2]);
    t++;
    sort(a+1,a+n+1,cmp6);
    check(dv[t][0],dv[t][1],dv[t][2]);
    t++;
    sort(a+1,a+n+1,cmp7);
    check(dv[t][0],dv[t][1],dv[t][2]);
    t++;
    sort(a+1,a+n+1,cmp8);
    check(dv[t][0],dv[t][1],dv[t][2]);
    t++;

    cout<<ans<<endl;
    return 0;
}


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

int main(){
  int64_t n;
  cin >> n;
  int64_t a=0,c=0;
  while(a<n){
    c++;
    a+=c;
  }
  while(n>0&&c>0){
    if(n>=c){
      cout << c << endl;
      n-=c;
    }
    c--;
  }
  return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <fstream>
#include <numeric>
using namespace std;
typedef long long int ll;

#define EPS (1e-7)
#define INF 1e18
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define PI (acos(-1))

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

int main() {
    string s;
    cin >> s;
    string ans = s[0] == s[2] ? "Yes" : "No";
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 100000000



int main(){
	
	string S;
	cin>>S;
	
	if(S=="Sunny"){
		cout<<"Cloudy"<<endl;
	}
	else if(S=="Cloudy"){
		cout<<"Rainy"<<endl;
	}
	else if(S=="Rainy"){
		cout<<"Sunny"<<endl;
	}
	
	
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 200;
const int MAXW = 20000;
int T[MAXN][MAXW];

int W,N;
int M[MAXN]; int V[MAXN];



void solve()
{
	for(int i = 1; i <= N; i++)
		for(int j = 1; j<= W; j++)
		{
			if(j<M[i])
				T[i][j] = T[i-1][j];
			else
				T[i][j] = max(T[i-1][j],T[i-1][j-M[i]]+V[i]);
		}
	cout << T[N][W]<<endl;
}

int main()
{
	
	cin >> N >> W;
	fill(*T,*(T)+W+1,0);
	for(int i = 1; i <= N; i++)
		cin >> V[i] >> M[i];

	solve();
}

Measured memory_bytes: 7372
#include<iostream>
#include<climits>
using namespace std;
int main()
{
    int n,k;
    cin>>n>>k;
    int *height=new int[n];
    int *dp=new int[n+1];
    for(int i=1;i<=n;i++)
    {
        cin>>height[i];
    }
    dp[1]=0;
    for(int i=2;i<=n;i++)
    {
        dp[i]=INT_MAX;
        for(int j=i-1;j>=1 && (i-j)<=k ;j--)
        {
            dp[i]=min(dp[i],abs(height[i]-height[j])+dp[j]);
        }
    }
    cout<<dp[n];
    return 0;
}



Measured memory_bytes: 1024
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let v = read_vec::<i64>();
    let (t1, t2) = (v[0], v[1]);
    let v = read_vec::<i64>();
    let (a1, a2) = (v[0], v[1]);
    let v = read_vec::<i64>();
    let (b1, b2) = (v[0], v[1]);

    let mut c1 = (a1 - b1) * t1;
    let mut c2 = (a2 - b2) * t2;
    if c1 < 0 {
        c1 *= -1;
        c2 *= -1;
    }
    if c2 > -c1 {
        println!("0");
        return;
    }
    if c1 == -c2 {
        println!("infinity");
        return;
    }
    debug!(c1, c2);
    let rev_num = c1 / (-c1 - c2);
    if c1 % (-c1 - c2) == 0 {
        println!("{}", 2 * rev_num);
        return;
    }
    println!("{}", 2 * rev_num + 1);
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


Measured memory_bytes: 4352
import sys

n=int(input())
l=["".join(sorted(sys.stdin.readline().strip())) for i in range(n)]


res={}
ans=0
 
for j in range(n):
    ll=list(l[j])
    ll.sort()
    aa="".join(ll)
    if aa in res:
        ans+=res[aa]
        res[aa]+=1
    else:
        res[aa]=1

print(int(ans))


Measured memory_bytes: 25036