akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define MOD 998244353
#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>b;--i)
#define vi vector<int>
#define vl vector<ll>
#define ld long double
#define vvi vector<vector<int>>
#define vvl vector<vector<long long>>
#define pii pair<int,int>
#define pll pair<long,long>
#define vpii vector<pii>
#define vpll vector<pll>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define PI 3.1415926535897932384626433832795
#define fix(f,n) fixed<<setprecision(n)<<f
#define all(x) x.begin(),x.end()
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

ll newmod(ll a,ll b)
 {
  return ((a%b)+b)%b;
}




ll powM(ll a,ll b,ll m )
{ 
  a%=m;
  ll ans=1;
  while(b>0)
  {
    if(b&1)ans=ans*a%m;
    a=a*a%m;
    b>>=1;
  }

return ans;
}

ll pow(ll a,ll b)
{ 
  
  ll ans=1;
  while(b)
  {
    if(b&1)ans=ans*a;
    a=a*a;
    b>>=1;
  }

return ans;
}


/*const int N=200000;

ll fac[N+1];
ll inv[N+1];
ll p=998244353;

ll c(ll a, ll b,ll m)
{
  if(a<b)return 0;
  return (fac[a]*inv[b]%m)*(inv[a-b])%m;
}

void fill()
{
inv[0]=1;
fac[0]=1;

for(int i=1;i<=N;i++)
{
  fac[i]=fac[i-1]*i%p;
  inv[i]=powM(fac[i],p-2,p);
}

}
*/
//ld dp[2001][2001];

//ll dp[3001][3001];  // dp[i][j] ways to make sum i using j numbers.


int main()
{  fast

ll n,s;
cin>>n>>s;



ll a[n+1]={};



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

//sort(all(a));
ll dp[n+1][s+1]={};

//cout<<dp[3][4]<<"\n";

dp[0][0]=powM(2,n,MOD);

for(int i=1;i<=n;i++)
{
  for(int j=0;j<=s;j++)
  {
     dp[i][j]+=dp[i-1][j];  //not choosing the element.

    if(j>=a[i]) 
      dp[i][j]+=dp[i-1][j-a[i]]*powM(2,MOD-2,MOD)%(MOD);  //choosing it ,so multplying with 2^(n-i).


    dp[i][j]=newmod(dp[i][j],MOD);
  }
}

//    O(N.S).

cout<<dp[n][s]<<"\n";

 return 0;

}


Measured memory_bytes: 74040
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define LINF 1LL<<60
struct edge {
	int u;
	int v;
	int cost;
	edge() {}
	edge(int u, int v, int cost) :u(u), v(v), cost(cost) {}
};
int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	ll N; cin >> N;
	vector<vector<edge>> G(N);
	for (int i = 0; i < N - 1;i++) {
		int a, b, c; cin >> a >> b >> c;
		a--; b--;
		G[a].push_back(edge(a, b, c));
		G[b].push_back(edge(b, a, c));
	}
	ll Q, K; cin >> Q >> K;
	K--;
	vector<ll> dist(N, LINF);
	queue<int> q;
	dist[K] = 0; q.push(K);
	while (!q.empty()) {
		auto n = q.front(); q.pop();
		for (auto e : G[n]) {
			if (dist[e.v] > dist[e.u] + e.cost) {
				dist[e.v] = dist[e.u] + e.cost;
				q.push(e.v);
			}
		}
	}
	for (int i = 0; i < Q;i++) {
		int x, y; cin >> x >> y; x--; y--;
		cout << dist[x] + dist[y] << endl;
	}
	return 0;
}

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

// #define int long long
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;

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

const ll INF = 1e15;
const int MOD = 1e9+7;
const ll LINF = 1e18;

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

ll ngcd(vector<ll> a) {
  ll res = a[0];
  for(ll i=1; i<a.size() && res!=1; i++) res = gcd(a[i], res);
  return res;
}
ll nlcm(vector<ll> a){
  ll res = a[0];
  for(ll i=1; i<a.size(); i++) res = lcm(a[i], res);
  return res;
}
bool is_prime(ll n) {
  if(n < 2) return false;
  for (ll i = 2; i * i <= n; i++) if (n % i == 0) return false;
  return true;
}
ll digsum(ll n) {
  ll res=0;
  while(n) res += n%10, n /= 10;
  return res;
}
ll digcnt(ll n){
  ll res=0;
  while(n) res++, n /= 10;
  return res;
}
vector<ll> divisor(ll n) {
  vector<ll> res;
  for (ll i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      res.push_back(i);
      if (i != n / i) res.push_back(n / i);
    }
  }
  return res;
}
map<ll, ll> prime_factor(ll n) {
  map<ll, ll> res;
  for (ll i = 2; i * i <= n; i++) {
    while (n % i == 0) ++res[i], n /= i;
  }
  if (n != 1) res[n] = 1;
  return res;
}

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  
  ll n,k; cin>>n>>k;
  ll sum=0;
  vll a(n);
  rep(i,n){
    cin>>a[i];
    sum+=a[i];
  }
  
  ll ans=1;
  auto div=divisor(sum);
  sort(div.rbegin(),div.rend());
  for(auto e: div){
    ll cnt=LINF;
    vll b(n);
    rep(i,n) b[i]=a[i]%e;
    vsort(b);
    ll plus=0, minus=0;
    rep(i,n) plus+=e-b[i];
    rep(i,n){
      minus+=b[i];
      plus-=(e-b[i]);
      if(plus==minus){
        if(plus<=k) chmax(ans,e);
      }
    }
  }
  cout<<ans<<endl;
}

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

int main(){
    ll A; cin >> A;
    string B; cin >> B;
    ll B100 = 100 * (B[0] - '0') + 10 * (B[2] - '0') + (B[3] - '0');
    cout << A * B100 / 100 << endl;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1LL << 62;

int n;
string s;

void input() {
    cin >> n >> s;
}

void solve() {
    string findWord("ABC");
    int count = 0;
    size_t pos = s.find(findWord);
    while(pos != string::npos) {
        pos = s.find(findWord, pos + findWord.length());
        ++count;
    }
    cout << count << endl;

}



int main() {
    input();
    solve();
}


Measured memory_bytes: 768
#include<bits/stdc++.h>
using namespace std;
inline int read(){
	char c=getchar();int t=0,f=1;
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){t=(t<<3)+(t<<1)+(c^48);c=getchar();}
	return t*f;
}
char s[5],t[5];
int main(){
	scanf("%s",s+1);
	scanf("%s",t+1);
	int ans=0;
	for(int i=1;i<=3;i++)if(s[i]==t[i])ans++;
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 256
#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 n,m;
    cin>>n>>m;
    vector<int>x(m);
    vector<int>xl(m-1);
    rep(i,m){
        cin>>x[i];
    }
    if(m==1){
        cout<<0<<endl;
        return 0;
    }
    if(n>=m){
        cout<<0<<endl;
        return 0;
    }
    int ans=0;
    sort(x.begin(),x.end());
    rep(i,m-1){
        xl[i]=abs(x[i]-x[i+1]);
        ans+=xl[i];
    }
    sort(xl.rbegin(),xl.rend());
    if(n>1){
        rep(i,n-1){
            ans-=xl[i];
        }
    }
    if(ans>0)cout<<ans<<endl;
    else cout<<0<<endl;
}


Measured memory_bytes: 1024
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(f.readLine());

        int n = Integer.parseInt(st.nextToken());

        long[][] happinessOptions = new long[n][3];

        // int[] chosenOption = new int[n]; // record which activity has been chosen, a: 0, b: 1, c: 2 (WRONG APPROACH)

        // long[] maxHappiness = new long[n]; // maximum happiness on ith day


        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(f.readLine());
            for (int j = 0; j < 3; j++) {
                long k = Long.parseLong(st.nextToken());
                happinessOptions[i][j] = k;
            }
        }

        /*for (int i = 0; i < 3; i++) {
            if (happinessOptions[0][i] > maxHappiness[0]){
                maxHappiness[0] = happinessOptions[0][i];
                chosenOption[0] = i;
            }
        }

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                if (j != chosenOption[i - 1] && happinessOptions[i][j] + maxHappiness[i - 1] > maxHappiness[i]) {
                    maxHappiness[i] = happinessOptions[i][j] + maxHappiness[i - 1];
                    chosenOption[i] = j;
                }
            }
        }*/

        // System.out.println(maxHappiness[maxHappiness.length - 1]);
        // WRONG IDEA: GREEDY PROBLEM


        long[][] maxHappiness = new long[n][3]; // maximum happinesses on ith day

        maxHappiness[0] = happinessOptions[0];

        for (int i = 1; i < maxHappiness.length; i++) {
            for (int j = 0; j < 3; j++) {
                if(j == 0) {
                    maxHappiness[i][j] = Math.max(maxHappiness[i-1][1], maxHappiness[i-1][2]) + happinessOptions[i][j];
                } else if (j == 1){
                    maxHappiness[i][j] = Math.max(maxHappiness[i-1][0], maxHappiness[i-1][2]) + happinessOptions[i][j];
                } else if (j == 2){
                    maxHappiness[i][j] = Math.max(maxHappiness[i-1][1], maxHappiness[i-1][0]) + happinessOptions[i][j];
                }
            }
        }

        System.out.println(String.valueOf(  Math.max(Math.max(maxHappiness[n-1][0], maxHappiness[n-1][1]), maxHappiness[n-1][2])  ) );
    }
}

Measured memory_bytes: 48200
#include <stdio.h>
 
int main(){
    int a[100]={};
    int n;
    int i;
    while(scanf("%d", &n)!=EOF)
    {
        a[n]++;
    }
    int MAX=0;
    for(i=0;i<100;i++)
    {
        if(MAX<a[i])
        {
            MAX=a[i];
        }
    }
    for(i=0;i<100;i++)
    {
        if(a[i]==MAX)
        {
            printf("%d\n", i);
        }
    }
    return 0;
}

Measured memory_bytes: 592
#include<iostream>
#include<vector>
#include<cstring>

long long owData[4001];
std::vector<int> used;

int main(){
  long long x,input[3];
	bool Person;
	while( std::cin>>x , x ){
		Person=false;
		used.clear();
		memset(owData,0,sizeof(owData));
		while( x-- ){
			std::cin>>input[0]>>input[1]>>input[2];
			if( owData[input[0]] == 0 )used.push_back(input[0]);
			owData[input[0]]+=input[1]*input[2];
		}
		for(auto it = used.begin(); it != used.end(); ++it ){
			if( owData[*it] >= 1000000 )
				std::cout<< *it <<std::endl, Person=true ;
		}
		if(!Person)std::cout<<"NA"<<std::endl;
	}
	return 0;
}

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

const int mod = 1000000007;
struct mint {
  ll x;  // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint& operator+=(const mint a) {
    if((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if((x += mod - a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const { return mint(*this) += a; }
  mint operator-(const mint a) const { return mint(*this) -= a; }
  mint operator*(const mint a) const { return mint(*this) *= a; }
  mint pow(ll t) const {
    if(!t) return 1;
    mint a = pow(t >> 1);
    a *= a;
    if(t & 1) a *= *this;
    return a;
  }
  // for prime mod
  mint inv() const { return pow(mod - 2); }
  mint& operator/=(const mint a) { return *this *= a.inv(); }
  mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }
mint fact(int n) {
  if(n == 1 || n == 0) return 1;
  mint res = n;
  return res * fact(n - 1);
}

int main() {
  ll n;
  cin >> n;
  vl c(n);
  rep(i, n) cin >> c[i];
  vl last(n), lc(2e5 + 1, 0);
  rep(i, n) {
    last[i] = lc[c[i]];
    lc[c[i]] = i + 1;
  }
  vector<mint> dp(n + 1, 0);
  dp[0] = 1;
  rep(i, n) {
    if(last[i] == 0 || last[i] == i)
      dp[i + 1] = dp[i];
    else
      dp[i + 1] = dp[i] + dp[last[i]];
  }
  cout << dp[n] << endl;
}

Measured memory_bytes: 9604
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e16;
const ll mod = 1000000007;
#define rep(i, n) for (int i = 0; i < (ll)(n); i++)

int main() {
  string a, b, c; cin >> a >> b >> c;
  ll loc_a = 0, loc_b = 0, loc_c = 0;
  char ch = 'a';
  while (true) {
    if (ch == 'a') {
      if (loc_a == a.size()) {
        cout << 'A' << endl;
        break;
      } else {
        ch = a.at(loc_a);
        loc_a++;
      }
    } else if (ch == 'b') {
      if (loc_b == b.size()) {
        cout << 'B' << endl;
        break;
      } else {
        ch = b.at(loc_b);
        loc_b++;
      }
    } else {
      if (loc_c == c.size()) {
        cout << 'C' << endl;
        break;
      } else {
        ch = c.at(loc_c);
        loc_c++;
      }
    }
  }
}

Measured memory_bytes: 3584
import java.math.BigDecimal;
import java.math.MathContext;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		BigDecimal n = BigDecimal.valueOf(sc.nextDouble());
		sc.close();
		System.out.println(func(n));
	}

	public static BigDecimal func(BigDecimal n) {
		BigDecimal x = n.divide(BigDecimal.valueOf(3), MathContext.DECIMAL32);

		return x.multiply(x).multiply(x);
	}
}


Measured memory_bytes: 23380
#include<iostream>
#include <algorithm>
#include<string>
#include <bitset>
#include <vector>
#include <functional>
#include <climits>
#include <iomanip>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <numeric>
#include <stack>
#include <map> // pair
#include <cstdlib>  // abs() for integer
#include <cmath>    // abs() for float, and fabs()
typedef std::stack<int> IntStack;
typedef std::stack<char> charStack;
#define START 0
#define FORWARD 1
#define BACK 2
using namespace std;
using ll = long long;
typedef pair <ll, ll > pll;
bool comp(const pll &a, const pll &b) {
	return a.first < b.first;
}
//*********************************************************
// 最大公約数（Greatest Common Divisor）を返す。
// 引数に０がある場合は０を返す。
//*********************************************************
ll gcd(ll a, ll b)
{
	ll tmp, r;
	if (a < b) {
		tmp = a;
		a = b;
		b = tmp;
	}

	/* ユークリッドの互除法 */
	r = a % b;
	while (r != 0) {
		a = b;
		b = r;
		r = a % b;
	}
	return b;
	//// 引数に０がある場合は０を返す
	//if ((0 == m) || (0 == n))
	//	return 0;

	//// ユークリッドの方法
	//while (m != n)
	//{
	//	if (m > n) m = m - n;
	//	else         n = n - m;
	//}
	//return m;
}//gcd

int main()
{
	ll a = 0, b = 0, c = 0, d = 0, e = 0, f = 0, g = 0, h = 0, ans = 0;
	ll x[200004] = {};
	ll y[200004] = {};
	ll z[2003][2003] = { {} };
	vector<tuple<ll, ll>> vec;
	string s;
	string t;
	//IntStack yStack;
	//charStack Stack;
	//vector<pair<int, int> > pairs(a);
	//cout << LLONG_MAX<< endl;

	cin >> a;
	for (int i = 0; i < a; i++)
	{
		cin >> x[i];
	}
	for (int i = 1; i < a-1; i++)
	{
		if (min({ x[i-1], x[i], x[i+1] }) != x[i]&& max({ x[i - 1], x[i], x[i + 1] }) != x[i])
		{
			ans++;
		}
	}


	cout << ans << endl;


	////std::cout << std::fixed;
	//cout << std::setprecision(20) << << endl;
	//cout << d+1 << endl;
	//cout << "" << endl;

	return 0;
}
//sort(x, x + a, std::greater<ll>());

//char型の文字数字は、-'0'で数値に変換できる
//accumulate(x, x + a, 0);//int型までの配列の合計
//memcpy(x, visited, sizeof(ll)*n);
//void kansuu(ll num, ll visited[10]) {}
//kansuu(1, zz);
//cout << setprecision(15) << v << endl;
//cout << char(z - 'a');
//log10(i) + 1 //10進数の桁数を取得
//
//int temp;
//for (int i = 0; i < n - 1; i++) {
//	for (int j = n - 1; j > i; j--) {
//		if (w[j - 1] < w[j]) {  /* 前の要素の方が大きかったら */
//			temp = w[j];        /* 交換する */
//			w[j] = w[j - 1];
//			w[j - 1] = temp;
//		}
//	}
//}
//
//最小公倍数
//ll x = a * b;
//ll tmp;
///* 自然数 a > b を確認・入替 */
//if (a<b) {
//	tmp = a;
//	a = b;
//	b = tmp;
//}
///* ユークリッドの互除法 */
//ll r = a % b;
//while (r != 0) {
//	a = b;
//	b = r;
//	r = a % b;
//}
//a = x / b;//答え


/*vector<pair<ll, ll> > hoges(a);
for (int i = 0; i < a; i++)
{
cin >> x[i];
cin >> y[i];
hoges[i] = make_pair(x[i], y[i]);
}
sort(hoges.begin(),hoges.end(),comp);
for (int i = 0; i < a; i++)
{
if (hoges[i].second>=b)
{
ans += hoges[i].first*b;
break;
}
else
{
ans += hoges[i].first*hoges[i].second;
b -= hoges[i].second;

}
}*/

Measured memory_bytes: 1792
//https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

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

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

//

use std::cmp::{max, min};

fn run() {
    input! {
        n: usize,
        k: usize,
        q: usize,
        a: [u32; n],
    }
    let mut b = vec![];
    for i in 0..n {
        b.push((a[i], i));
    }
    b.sort();
    let mut remove = vec![false; n];
    let mut ans = 1_000_000_000;
    for i in 0..n {
        let mut c = vec![];
        let mut p = vec![];
        for j in 0..n {
            if remove[j] {
                p.sort();
                p.reverse();
                while p.len() >= k {
                    c.push(p.pop().unwrap());
                }
                p.clear();
            } else {
                p.push(a[j]);
            }
        }
        p.sort();
        p.reverse();
        while p.len() >= k {
            c.push(p.pop().unwrap());
        }
        c.sort();
        if c.len() < q {
            break;
        }
        ans = min(ans, c[q - 1] - c[0]);
        remove[b[i].1] = true;
    }
    println!("{}", ans);
}

fn main() {
    run();
}


Measured memory_bytes: 4352
num = gets.to_i
i = 1
sum = 0

while i <= num do
  if i % 3 == 0 && i % 5 == 0
    "FizzBuzz"
  elsif i % 3 == 0
    "Fizz"
  elsif i % 5 == 0
    "Buzz"
  else
    sum += i
  end
  i += 1
end

puts sum


Measured memory_bytes: 14388
#include<bits/stdc++.h>
#include<boost/multiprecision/cpp_int.hpp>
using namespace std;
using namespace boost::multiprecision;
#define BEGIN ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define END return EXIT_SUCCESS
#define rep(I,N) for(auto I=0;I<(N);++I)
#define up(I,A,B) for(auto I=(A);I<=(B);++I)
#define dw(I,A,B) for(auto I=(A);I>=(B);--I)
#define all(C) (C).begin(),(C).end()
#define rall(C) (C).rbegin(),(C).rend()
#define ft first
#define sd second
#define mp make_pair
#define mt make_tuple
#define pf push_front
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define rs resize
typedef long long ll;
typedef unsigned long long ull;
template<class T>inline void                                      in(T &p){cin>>p;}
template<class T1,class T2>inline void                            in(T1 &p1,T2 &p2){cin>>p1>>p2;}
template<class T1,class T2,class T3>inline void                   in(T1 &p1,T2 &p2,T3 &p3){cin>>p1>>p2>>p3;}
template<class T1,class T2,class T3,class T4>inline void          in(T1 &p1,T2 &p2,T3 &p3,T4 &p4){cin>>p1>>p2>>p3>>p4;}
template<class T1,class T2,class T3,class T4,class T5>inline void in(T1 &p1,T2 &p2,T3 &p3,T4 &p4,T5 &p5){cin>>p1>>p2>>p3>>p4>>p5;}
template<class T>inline void                                      ins(T &p){for_each(all(p),in<decltype(p[0])>);}
template<class T>inline void                             out(T p){cout<<p<<endl;}
template<class T1,class T2>inline void                   out(T1 p1,T2 p2){cout<<p1<<" "<<p2<<endl;}
template<class T1,class T2,class T3>inline void          out(T1 p1,T2 p2,T3 p3){cout<<p1<<" "<<p2<<" "<<p3<<endl;}
template<class T1,class T2,class T3,class T4>inline void out(T1 p1,T2 p2,T3 p3,T4 p4){cout<<p1<<" "<<p2<<" "<<p3<<" "<<p4<<endl;}
inline                                              void out(double p){printf("%.10f\n",p);}
template<class T>inline                             void outs(T p){for_each(all(p),out<decltype(p[0])>);}

inline void solve(void){
  string T="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  int N;string S;in(N,S);
  rep(i,S.size()){
    cout<<T[(S[i]-'A'+N)%26];
  }
  cout<<endl;
}
int main(int argc,char**argv){
  BEGIN;
  solve();
  END;
}


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

using namespace std;

int main(){
    vector<int>v;
    for(int i=0;i<3;i++){
        int a;
        cin >> a;
        v.push_back(a);
    }
    sort(v.begin(),v.end());
    for(int i=0;i<3;i++){
        cout << v[i];
        if(i!=2) cout << " ";
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 1220
#include<stdio.h>

int calculater(int s){
  int j;
  if(s == 2){
    return 1;
  }
   if(s%2 == 0){
      return 0;
    }
  for(j=3;j*j<=s;j++){
    if(s%j == 0){
      return 0;
    }
  }
  return 1;
}

int main(){
  int i, n, s, count=0;

  scanf("%d", &n);

  for(i=0;i<n;i++){
    scanf("%d",&s);
    if(calculater(s) == 1) count++;
  }

  printf("%d\n",count);

  return 0;
}
      
  



Measured memory_bytes: 2104
N=int(input())
A=[int(x) for x in input().split()]
B=[int(x) for x in input().split()]
C=[int(x) for x in input().split()]
score=0
pre=0
pre_a=-100
for i,a in enumerate(A):
    score+=B[a-1]
    if pre_a+1==a:
        score+=C[pre_a-1]
    pre=i
    pre_a=a
print(score)

Measured memory_bytes: 3188
#include<string>
#include<cstdio>
#include<cctype>
#include<iostream>
#include <algorithm>
#include<cmath>
#include<queue>
using namespace std;

int main(){
    int m,o,ans;
    while(1){
    o=0;
    ans=0;
    cin >> m;
    if(m==0)break;
    o=1000-m;
    if(o>500){
        o-=500;
        ans++;
    }
    if(o / 100 > 0){
        ans+=o/100;
        o%=100;
    }
    if(o>50){
        o-=50;
        ans++;
    }
    if(o / 10 > 0){
    ans+=o/10;
    o%=10;
    }
    if(o>4){
        ans++;
        o-=5;
    }
    ans+=o;
    cout <<ans<<endl;
    }
    return 0;
}

Measured memory_bytes: 1160
#include <stdio.h>

int main() {

	int n ;
	scanf("%d", &n) ;

	int sum_a = 0, sum_b = 0 ;

	while (n > 0) {
		int i ;
		int a, b ;
		for (i = 0 ; i < n ; i++) {
			scanf("%d%d", &a, &b) ;
			if (a > b) sum_a += a + b ;
			else if (a < b)	sum_b += a + b ;
			else if (a == b) {
				sum_a += a ;
				sum_b += b ;
			}
		}
		printf("%d %d\n", sum_a, sum_b) ;

		sum_a = sum_b = 0 ;

		scanf("%d", &n) ;

	}


	return 0 ;

}

Measured memory_bytes: 600
#include <iostream>
#include <cmath>
#include <iomanip>
#include <limits>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <list>
#include <cctype>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i=0;i<(n);i++)

locale l = locale::classic();

int main(){
    int n;
    cin >> n;
    int v[n],c[n];
    rep(i,n) cin >> v[i];
    rep(i,n) cin >> c[i];
    int ans=0;
    rep(i,n) if(v[i]-c[i]>0) ans += v[i]-c[i];
    cout << ans << endl;
}

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

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

bool used[100005];
vector < pair<long long,long long> > g[100005];
long long dist[100005];

void dfs(int pos,long long depth)
{
	if(dist[pos] != -1)
		return;
	dist[pos] = depth;
	for(int i = 0;i < g[pos].size();i++)
		dfs(g[pos][i].first,depth + g[pos][i].second);
}

int main(void)
{
	long long N;
	cin >> N;
	memset(dist,-1,sizeof(dist));
	REP(i,N-1)
	{
		long long x,y,z; 
		cin >> x >> y >> z;
		x--; y--;
		g[x].push_back({y,z});
		g[y].push_back({x,z});
	}
	int T,K;
	cin >> T >> K;
	dfs(K-1,0);
    while(T--){
    	long long x,y;
    	cin >> x >> y;
    	x--; y--;
    	cout << dist[x]+dist[y] << endl;
	}
	return 0;
}

Measured memory_bytes: 14336
import numpy as np
N = int(input())
A = np.array([0] + [int(x) for x in input().split()] + [0])
total = np.abs(np.diff(A)).sum()
saved = np.abs(A[1:-1] - A[:-2]) + np.abs(A[1:-1] - A[2:]) - np.abs(A[:-2] - A[2:])
answer = total - saved
print(*answer, sep='\n')

Measured memory_bytes: 24808
n=int(input())
x=list(map(int,input().split()))
imax=int(max(x))
imin=int(min(x))
lis=[]
re=0
for k in range(imin,imax+1):
  for i in x:
    re=re+(i-k)**2
  lis.append(re)
  re=0
print(min(lis))

Measured memory_bytes: 3064
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<stdio.h>
#include<queue>
#include <climits>
#include <map>
#include <set>
const int mod = 1e9 + 7;
const int INF = 1 << 20;
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main()
{
    int n; cin >> n;
    for(int i = 0; i < n; i++){
        ll p; cin >> p;
        ll y; cin >> y;
        ll m; cin >> m;
        ll ans = 0;
        for(int j = 0; j < m; j++){
            ll a; cin >> a;
            double b; cin >> b;
            ll c; cin >> c;
            ll now = p;
            ll add = 0;
            if(a == 0){
                for(int k = 0; k < y; k++){
                    add += now * b;
                    now -= c;
                }
                ans = max(ans,now+add);
            }else{
                for(int k = 0; k < y; k++){
                    now += now*b;
                    now -= c;
                }
                ans = max(ans,now);
            }
        }
        cout << ans << endl;
    }
}


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

#define int long long

signed main()
{
	int x,y,a,b,c,s=0;
	cin >> x >> y >> a >> b >> c;
	priority_queue<pair<int,int> > h;
	
	while(a--)
	{
	    int war;
	    cin >> war;
	    h.push(make_pair(war,1));
	}
	
	while(b--)
	{
	    int war;
	    cin >> war;
	    h.push(make_pair(war,2));
	}
	while(c--)
	{
	    int war;
	    cin >> war;
	    h.push(make_pair(war,3));
	}
	int z=x+y;
	int san=0;
	while (z)
	{
		pair<int,int> f=h.top();
		h.pop();
		if (f.second==3){
			san+=f.first;
			--z;
		}
		else if (f.second==1 && x){
			san+=f.first;
			--x;
			--z;
		}
		else if (f.second==2 && y){
			san+=f.first;
			--y;
			--z;
		}
	}
	cout << san;
	return 0;
}


Measured memory_bytes: 10604
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
P = [None] + [int(x) for x in input().split()]
p_to_i = [None] * (N+1)
for i,x in enumerate(P[1:],1):
    p_to_i[x] = i

# 大きい数から挿入していく
# 左隣にあるインデックスを取得できるようにしておく
# そのために、[1,i]内で書き込んだ数の個数を獲得できるBITを持つ

# BITは一番最後の1ビットの位置が重要なので0ではなく1始まり。そのためNまでループする
def BIT_add(i):
    while i <= N:
        tree[i] += 1
        i += i&(-i)

def BIT_sum(i):
    s = 0
    while i:
        s += tree[i]
        i -= i&(-i)
    return s

def BIT_search(x):
    # 二分探索。和がx以上となる最小のインデックス(>= 1)を返す
    i = 0
    s = 0
    step = 1<<(N.bit_length()-1)
    while step:
        if i+step <= N and s + tree[i+step] < x:
            i += step
            s += tree[i]
        step >>= 1
    return i+1
    left = 0
    right = N
    while right - left > 1:
        mid = (left + right) // 2
        if BIT_sum(mid) >= x:
            right = mid
        else:
            left = mid
    return right

tree = [0] * (N+1)
answer = 0
for x in range(N,0,-1):
    c = p_to_i[x]
    L = BIT_sum(c) # 左にある既に書き込んだ数の個数
    BIT_add(c)
    R = N-x-L # 右にある既に書き込んだ数の個数
    a = BIT_search(L-1) if L >= 2 else 0
    b = BIT_search(L) if L >= 1 else 0
    d = BIT_search(L+2) if R >= 1 else N+1
    e = BIT_search(L+3) if R >= 2 else N+1
    coef = 0
    if b != 0:
        # [b,c]を含むようにする。(a,b) と(c,d)が自由
        coef += (b-a) * (d-c)
    if d != 0:
        # [c,d]を含むようにする。
        coef += (e-d) * (c-b)
    answer += x * coef
print(answer)





Measured memory_bytes: 19920
use proconio::input;
use std::collections::BTreeMap;

fn main() {
    input! {
        n: u32,
        a: [u64; n],
        q: u32,
    }
    let mut sum = 0;
    let mut a_count = BTreeMap::new();
    for v in a {
        *a_count.entry(v).or_insert(0) += 1;
        sum += v;
    }
    for _ in 0..q {
        input!{
            b: u64,
            c: u64,
        }
        if a_count.contains_key(&b) {
            sum -= b * a_count[&b];
            sum += c * a_count[&b];
            *a_count.entry(c).or_insert(0) += a_count[&b];
            *a_count.entry(b).or_insert(0) = 0;
        }
        println!("{}", sum);
    }
}


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

int n,m,u,v;
int f[100005];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void join(int x,int y){
	int fx=find(x),fy=find(y);
	if(fx!=fy)f[fx]=fy;
}
vector<int>e[100005];
vector<int>e2[100005];
bool ok[100005];
vector<int>q;
void dfs(int i){
	ok[i]=1;
	for(int j=0;j<e[i].size();j++)
		if(!ok[e[i][j]])dfs(e[i][j]);
	q.push_back(i);
}
void dfs2(int i,int top){
	ok[i]=0;
	for(int j=0;j<e2[i].size();j++)
		if(ok[e2[i][j]])dfs2(e2[i][j],top);
	join(i,top);
}
void solve(){
	for(int i=0;i<=n;i++)f[i]=i;
	for(int i=0;i<n;i++)if(!ok[i])dfs(i);
	for(int i=n-1;i>=0;i--)if(ok[q[i]])dfs2(q[i],q[i]);
}
int main(){
//	freopen("a.txt","r",stdin);
	cin.tie(0);
	cin>>n>>m;
	while(m--){
		cin>>u>>v;
		e[u].push_back(v);
		e2[v].push_back(u);
	}
	solve();
	cin>>m;
	while(m--){
		cin>>u>>v;
		if(find(u)!=find(v))cout<<0<<endl;
		else cout<<1<<endl;
	}
	return 0;
}


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

int main(){
  int N;
  cin >> N;
  string S;
  cin >> S;

  for(int i = 0;i < S.length();i++){
    std::cout << (char)(((char)(S[i]) + N - 'A') % 26 + 'A');
  }
  std::cout << std::endl;
}


Measured memory_bytes: 256
#include<cstdio>
#include<functional>
#include<algorithm>
using namespace std;
typedef pair<int,int> P;

int main(void)
{
	int a,b,d,r;
	double f;
	scanf("%d %d",&a,&b);
	d=a/b;
	r=a%b;
	f=(double)a/b;
	printf("%d %d %lf\n",d,r,f);
	return 0;
}


Measured memory_bytes: 2740
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
using System.Numerics;

namespace AtCoder
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        static long Mod = (long)1e9 + 7;
        static void Main(string[] args)
        {
            SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            Solve();
            Out.Flush();
            Read();
        }
        static void Solve()
        {
            var N = Sarray()[0];
            var Ti = Sarray();
            var Vi = Sarray();
            Vi = Vi.Concat(new long[] { 0 }).ToArray();
            for (var i = N - 1; 0 <= i; --i)
                Vi[i] = Min(Vi[i], Vi[i + 1] + Ti[i]);

            decimal Vl = 0, Vr = 0, sum = 0;
            for (var i = 0; i < N; ++i)
            {
                decimal men = 0;
                var t = Ti[i];
                if (Vi[i]+(decimal)0.1 < Vl) throw new Exception();
                if (Vi[i] <= Vi[i+1])
                {
                    Vr = Min(Vl + t, Vi[i]);
                    var Adt = Vr - Vl;
                    var Cst = t - Adt;
                    men = (Vl + Vr) * Adt / (decimal)2.0 + Cst * Vr;
                }
                else
                {
                    Vr = Min(Vi[i + 1], Vl + t);
                    decimal Vm = Vi[i];
                    decimal Adt = Vm - Vl;
                    decimal Dst = Vm - Vr;
                    if (t < Adt + Dst)
                    {
                        Adt = (t + Vr - Vl) / (decimal)2.0;//Vl+Adt'=Dst'+Vr,Adt'+Dst'=t
                        Dst = t - Adt;
                        Vm = Vl + Adt;
                    }
                    men = (Vl + Vm) * Adt / (decimal)2.0 + Vm * (t - Adt - Dst) + (Vm + Vr) * Dst / (decimal)2.0;
                }
                Vl = Vr;
                sum += men;
            }
            WriteLine($"{sum:f5}");
        }
    }
}

Measured memory_bytes: 28404
#import<stdio.h>
#import<queue>
int main(){std::queue<int>q;int w,h,f[484],i,j,a,b,t,x,z;char p[15];for(;scanf("%d%d ",&h,&w),h;){for(j=0;j<w+2;j++)f[j]=f[j-~h*22]=-9;for(i=1;i<=h;i++){for(j=1;j<=w;j++)f[x=i*22+j]=-1,z=getchar(),z-35?z>65?b=x:z>64?a=x:1:--f[x];f[i*22]=f[i*22-~w]=-9;getchar();}f[a]=t=0;q.push(0);for(q.push(a);a=q.front(),q.size()>1;q.pop())if(!a)++t,q.push(0);else for(i=4;i--;)if(f[x=a+" 57L"[i]-54]==-1)f[x]=t,q.push(x);q.pop();scanf("%s",p);for(a=t=0;!a;){x=b;z=0;for(i=0;!a&&p[i];i++){t++;f[j=b-54+"L65676 "[p[i]-50]]>-3?b=j:0;f[b]>=0&&t>=f[b]?a=b:0;f[b]>=0&&++z;}!z&!a&!p[i]&b==x&f[b]<0&&--a;}printf(a<0?"impossible\n":"%d %d %d\n",t,a/22-1,a%22-1);}}

Measured memory_bytes: 0
N, M = map(int, input().split())
sc = list(list(map(int, input().split())) for _ in range(M))

for i in range(1000):
    str_num = str(i)
    num_len = len(str_num)
    if num_len != N:
        continue
    for s, c in sc:
        if int(str_num[s - 1]) != c:
            break
    else:
        print(i)
        exit()

print("-1")


Measured memory_bytes: 3060
#include <stdio.h>
#include <math.h>



int main(void){
  
  int N;
  scanf("%d", &N);
  
  char c[N][N+1];
  
  int i;
  int j;
  
  int r[N];
  for( i = 0; i < N; i++ ){
    r[i] = 0;
  }
  
  int b;
  int idx[N];
  int num = 0;
  
  int cnt = 0;
  int max = 0;
  int ans = 0;
  
  for( i = 0; i < N; i++ ){
    scanf("%s", c[i]);
  }
  
  for( i = 0; i < N; i++ ){
    b = 0;
    for( j = 0; j < N; j++ ){
      if( c[i][j] == '#' ){
        r[j]++;
        b++;
      }
    }
    if( max < b ){
      num = 0;
      max = b;
      idx[0] = i;
    }
    else if( max == b ){
      num++;
      idx[num] = i;
    }
      
  }
  
  for( i = 0; i < N; i++ ){
    if( r[i] == N ) cnt++;
  }
  
  //printf("%d %d\n", max, cnt);
  
  if( max ){
    for( i = 0; i < N; i++ ){
      for( j = 0; j <= num; j++ ){
        if( c[i][idx[j]] == '#' ){
          max++;
          j = num + 1;
          i = N;
        }
      }
    }
    
    ans = 2*N - max - cnt + 1;
    
    printf("%d\n", ans);
    
  }
  
  else{ puts("-1");}  
  
  
  return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <array>
#include <list>
#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>
#include <cassert>
#include <random>
int main() {
	int n; std::cin >> n;
	std::string str; std::cin >> str;
	std::vector<std::vector<int>> next_position(str.size(), std::vector<int>(10, -1));
	next_position.back()[str.back() - '0'] = next_position.size() - 1;
	for (int i = next_position.size() - 2; i >= 0; --i) {
		next_position[i] = next_position[i + 1];
		next_position[i][str[i] - '0'] = i;
	}
	int count = 0;
	for (auto i = 0; i < 1000; ++i) {
		auto pos = 0; 
		auto val = i;
		auto j = 0;
		for (; j < 3 && pos < next_position.size() && next_position[pos][val % 10] != -1; ++j) {
			pos = next_position[pos][val % 10] + 1;
			val /= 10;
		}
		if (j == 3) {
			++count;
		}
	}
	std::cout << count << '\n';
}

Measured memory_bytes: 2432
#include<bits/stdc++.h>
using namespace std;
#define llt long long int
#define pb push_back
#define pii pair<int,int>
#define mk make_pair
#define ff first
#define ss second
#define mod 1000000007
int32_t main(){
    string s,t,u="";
    cin>>s>>t;
    int n=s.size(),m=t.size();
    vector<vector<pii > > dp(n+1,vector<pii >(m+1));
    for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++){
            if(i==0||j==0){
                dp[i][j]=mk(0,0);
            }
            else if(s[i-1]==t[j-1]){
                dp[i][j].ff=dp[i-1][j-1].ff+1;
                dp[i][j].ss=1;
            }
            else{
                if(dp[i-1][j].ff>=dp[i][j-1].ff){
                    dp[i][j].ff=dp[i-1][j].ff;
                    dp[i][j].ss=2;
                }
                else{
                    dp[i][j].ff=dp[i][j-1].ff;
                    dp[i][j].ss=3;
                }
            }
        }
    }
  /*  for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++){
            cout<<dp[i][j].ff<<","<<dp[i][j].ss<<"    ";
        }
        cout<<endl;
    }*/
    int i=n,j=m;
    while(i>0&&j>0){
        if(dp[i][j].ss==1){
            u+=s[i-1];
            i--;j--;
        }
        else if(dp[i][j].ss==2){
            i--;
        }
        else if(dp[i][j].ss==3){
            j--;
        }
        else{
            break;
        }
    }
    reverse(u.begin(),u.end());
    cout<<u;
    return 0;
}

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

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

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

    string a,b; cin >> a >> b;

    if(a.size() > b.size()) cout << "GREATER" << endl;
    else if(a.size() < b.size()) cout << "LESS" << endl;
    else{   
        if(a > b) cout << "GREATER" << endl;
        else if(a < b) cout << "LESS" << endl;
        else cout << "EQUAL" << endl;
    }

    return 0;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template<typename T1, typename T2>
inline bool cmn (T1& a, T2 b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template<typename T1, typename T2>
inline bool cmx (T1& a, T2 b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
class dijkstra {
  const int n, r;
  const vector<vector<pair<T, int>>>& grh;
  vector<T> dst;
  void cal () {
    priority_queue<
      pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>
      > que;
    que.emplace(0, r);
    while (!que.empty()) {
      T crd; int crr; tie(crd, crr) = que.top(), que.pop();
      if (!cmn(dst[crr], crd)) continue;
      for (auto e : grh[crr]) {
        T w; int nxt; tie(w, nxt) = e;
        T nxd = crd + w;
        if (nxd < dst[nxt]) que.emplace(nxd, nxt);
      }
    }
  }
  public:
    const T inf;
    dijkstra (
        const int r,
        const vector<vector<pair<T, int>>>& grh,
        const T inf = numeric_limits<T>::max()
      ) :
      n(grh.size()), r(r),
      grh(grh), dst(n, inf), inf(inf)
      {
        cal();
      }
    auto result () const {return dst;}
};
int main() {
  cin.tie(0); cin.sync_with_stdio(false);
  int n, m, r;
  cin >> n >> m >> r;
  vector<vector<pair<int, int>>> grh(n);
  for (int i = 0; i < m; i++) {
    int s, t; int d;
    cin >> s >> t >> d;
    grh[s].emplace_back(d, t);
  }
  dijkstra<int> dij(r, grh);
  auto inf = dij.inf;
  for (auto const& x : dij.result()) {
    cout << (x == inf ? "INF" : to_string(x)) << endl;
  }
  return 0;
}


Measured memory_bytes: 13964
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 200010
#define LL long long
LL ans;
int a[MAXN],b[MAXN],n,fa[MAXN],siz[MAXN];
int Find(int x)
{
	return fa[x]==x?x:fa[x]=Find(fa[x]);
}
void Union(int u,int v)
{
	u=Find(u),v=Find(v);
	if(u==v) return;
	fa[u]=v;
	siz[v]+=siz[u];
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		fa[i]=i,siz[i]=1;
		scanf("%d",&a[i]);
		b[a[i]]=i;
	}
	for(int i=n;i>=1;i--)
	{
		int p=b[i],sl=1,sr=1;
		if(a[p-1]>a[p])
		{
			sl+=siz[Find(a[p-1])];
			Union(a[p],a[p-1]);
		}
		if(a[p+1]>a[p])
		{
			sr+=siz[Find(a[p+1])];
			Union(a[p],a[p+1]);
		}
		ans+=1LL*i*sl*sr;
	}
	printf("%lld\n",ans);
}

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

int main(){
	string a;
	cin >> a;
	string b = "CODEFESTIVAL2016";
	int ans = 16;
	for(int i = 0; i < 16; i++){
		ans -= (a[i] == b[i]);
	}
	cout << ans << endl;
}


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

int main() {
    int n; cin>>n;
    int a,b;cin>>a>>b;
    
    int ans = 0;
    for(int i = 1; i<=n;++i){
        int tmp = i;
        int tmp2 = 0;
        while(tmp > 0){
            int x = tmp%10;
            tmp2 += x;
            tmp/=10;
        }
//      cout<<tmp2<<endl;
        if(tmp2>=a && tmp2 <=b)ans+=i;
    }
    cout<<ans<<endl;
	return 0;
}

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

int main(){
	int N;
	cin >> N;
	int ans=0;
	vector<int> V(N);
	vector<int> C(N);
	for(auto &i:V)cin >> i;
	for(auto &i:C)cin >> i;
	for(int i=0;i<N;i++){
		ans+=max(0,V[i]-C[i]);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;
int main(){
	int a,b;
	cin>>a>>b;
	if(a>b){
		cout<<"a > b"<<endl;
	}else if(a<b){
		cout<<"a < b"<<endl;
	}else if(a=b){
		cout<<"a == b"<<endl;
	}


	return 0;
}

Measured memory_bytes: 1156
n, k = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
tally = Hash.new { 0 }
a.each do |num|
  tally[num] += 1
end

sorted_tally_count = tally.values.sort

answer = 0

(sorted_tally_count.size - k).times do |num|
  answer += sorted_tally_count[num]
end

puts answer


Measured memory_bytes: 32880
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64
#define rep(i, n) for(int i=0; i<n; i++)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define SORT(x) sort(x.begin(), x.end())
#define GSORT(x) sort(x.begin(), x.end(), greater<int>())
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(), x.end()
#define V(T) vector<T>
typedef pair<int, int> P;
typedef pair<P, P> PP;
typedef vector<int> vi;
typedef vector<vi> vvi;
int max(int a, int b) {if(b>a) return b; else return a;}
int min(int a, int b) {if(b<a) return b; else return a;}


signed main() {
    string S;
    int N;
    cin >> N >> S;

    string res = "";
    rep(i, S.size()) {
        int c = int(S[i]+N);
        res += char((S[i]-'A'+N)%26) + 'A';
    }

    cout << res << endl;
    
    return 0;
}

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

template<class Ty>
using passive_queue = priority_queue<Ty, vector<Ty>, greater<Ty>>;

struct Problem {

	void Solve() {
		double L; cin >> L;
		L /= 3.0;
		L = L * L * L;
		cout << L << endl;
	}

	Problem();
};
int main() {
	unique_ptr<Problem> p(new Problem());
	p->Solve();
	return 0;
}
Problem::Problem() {
	cout << fixed << setprecision(10);
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var N = sc.ReadInt();
        var S = sc.ReadCharArray(N);
        var ans = "";
        if (S.Distinct().Count() == 3)
        {
            ans = "Three";
        }
        else
        {
            ans = "Four";
        }
        Console.WriteLine(ans);
    }
    static Scanner sc = new Scanner();
}

class Scanner
{
    string[] S = new string[0];
    int Index = 0;
    char[] Separators = new char[] { ' ' };

    public string Next()
    {
        if (this.Index < this.S.Length) return this.S[this.Index++];
        var line = "";
        while (line == "") line = Console.ReadLine();
        this.S = line.Split(this.Separators, StringSplitOptions.RemoveEmptyEntries);
        if (this.S.Length == 0) return this.Next();
        this.Index = 0;
        return this.S[this.Index++];
    }
    public string ReadStr()
    {
        return this.Next();
    }
    public char ReadChar()
    {
        return this.Next()[0];
    }
    public int ReadInt()
    {
        return int.Parse(this.Next());
    }
    public uint ReadUInt()
    {
        return uint.Parse(this.Next());
    }
    public long ReadLong()
    {
        return long.Parse(this.Next());
    }
    public double ReadDouble()
    {
        return double.Parse(this.Next());
    }
    public int[] ReadIntArray(int n)
    {
        var array = new int[n];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = this.ReadInt();
        }
        return array;
    }
    public long[] ReadLongArray(int n)
    {
        var array = new long[n];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = this.ReadLong();
        }
        return array;
    }
    public double[] ReadDoubleArray(int n)
    {
        var array = new double[n];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = this.ReadDouble();
        }
        return array;
    }
    public char[] ReadCharArray(int n)
    {
        var array = new char[n];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = this.ReadChar();
        }
        return array;
    }
    public string[] ReadStrArray(int n)
    {
        var array = new string[n];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = this.ReadStr();
        }
        return array;
    }
}


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

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

  vector<double> p(n);
  double sum = 0.0;
  for (int i = 0; i < n; i++)
  {
    int m;
    cin >> m;
    p[i] = (m+1)/2.0;
    if(i<k) sum+=p[i];
  }

  double ans;

  /* 累積和 */
  ans = 0.0;
  vector<double> rui(n+1);
  for (int i = 1; i <= n; i++)
  {
    rui[i] = rui[i-1] + p[i-1];
  }
  for (int i = 0; i <= n-k; i++)
  {
    double sum = rui[i+k]-rui[i];
    ans = max(ans,sum);
  }
  printf("%.10lf\n",ans);
}

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

int main() {
	ll H, W;
	cin >> H >> W;
	
	ll a, b, c, cnt, ans = H;
	for (ll i = 1;i < H;i++) {
		a = i * W;
		if ((H - i) % 2 == 0 || W % 2 == 0) {
			b = c = (H - i) * W / 2;
		}
		else {
			b = min(H - i, W)*(max(H - i, W) / 2);
			c = (H - i)*W - b;
		}
		cnt = max({ a,b,c }) - min({ a,b,c });
		ans = min(cnt, ans);
	}
	swap(H, W);
	for (ll i = 1;i < H;i++) {
		a = i * W;
		if ((H - i) % 2 == 0 || W % 2 == 0) {
			b = c = (H - i) * W / 2;
		}
		else {
			b = min(H - i, W)*(max(H - i, W) / 2);
			c = (H - i)*W - b;
		}
		cnt = max({ a,b,c }) - min({ a,b,c });
		ans = min(cnt, ans);
	}
	cout << ans << endl;
}

Measured memory_bytes: 256