akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

# define p(s) std::cout << s << endl;
# define printIf(j,s1,s2) cout << (j ? s1 : s2) << endl;
# define YES(j) cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
# define n_inf -(1 < <30);

int main()
{
    int n,m;cin >> n >> m;
    p((1900*m+100*(n-m))*pow(2,m));
} 

Measured memory_bytes: 256
#include<cstdio>
#include<vector>
#include<algorithm>
#include<utility>
#include<numeric>
#include<iostream>
#include<array>
#include<string>
#include<sstream>
#include<stack>
#include<queue>
#include<list>
#define _USE_MATH_DEFINES

#include<math.h>
#include<map>

#define SENTINEL 1000000001

#define min(a,b) (a)>(b)?(b):(a)
#define max(a,b) (a)>(b)?(a):(b)

using namespace std;

int G[101][101];

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

	for (int i = 0; i < n; i++)
	{
		int id, k;
		cin >> id >> k;

		for (int i = 0; i < k; i++)
		{
			int v;
			cin >> v;
			G[id][v] = 1;
		}
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			printf(j == 1 ? "%d" : " %d", G[i][j]);
		}
		printf("\n");
	}

	return 0;
}


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

class Program
{
    static void Main()
    {
		int[] a =Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
		var b = new List<int>();
		for(int i = a[0]<=a[1] ? a[0] : a[1]; i>0; i--)
		{
			if(a[0]%i==0 && a[1]%i==0) b.Add(i);
		}
      	Console.WriteLine(b[a[2]-1]);
    }
}


Measured memory_bytes: 27836
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    int n;
    while (cin >> n) {
        if(n >= 2800) {
            cout << "AGC" << endl;
        }else if(n < 2800 && n >= 1200) {
            cout << "ARC" << endl;
        }else{
            cout << "ABC" << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 256
//vec[i]の範囲外エラー表示
#define _GLIBCXX_DEBUG
//includeとusing
#include <bits/stdc++.h>
using namespace std;
//型名省略
template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;
using ll = long long;
using st = string;
using vl = vector<long long>;
using vvl = vector<vector<long long>>;
using vc = vector<char>;
using vvc = vector<vector<char>>;
using vs = vector<string>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using pll = pair<ll, ll>;
using pcc = pair<char, char>;
//定数
const ll INF = 1e9;
const ll MOD = 1e9+7;
const vl dx = {1,0,-1,0,1,0,-1,0};
const vl dy = {0,1,0,-1,0,1,0,-1};
//マクロ
#define rep(i,n) for(ll i = 0; i < (ll) n; i++)
#define rrep(i,n) for(ll i = (ll) n - 1; i >= 0;i--)
#define REP(i,x,n) for(ll i = (ll) x; i < (ll) n; i++)
#define RREP(i,x,n) for(ll i = (ll) n - 1; i >= x; i--)
#define each(i,A) for(ll i: (vl) A)
#define all(A) A.begin(), A.end()
#define Size(A) ll(A.size())
//入力
template<typename T> T input() {T x; cin >> x; return x;}
//正誤判定
void Yes(bool ans){cout << (ans? "Yes" : "No") << endl;}
void YES(bool ans){cout << (ans? "YES" : "NO") << endl;}
//余り切り上げ
ll ceil(ll a,ll b) {return (a + b - 1) / b;}
//最大値・最小値
template <typename T> bool chmax(T &a, const T& b) {if(a < b) {a = b; return true;} return false;}
template <typename T> bool chmin(T &a, const T& b) {if(a > b) {a = b; return true;} return false;}
//最大公約数
ll gcd(ll a,ll b){if(a<b)swap(a,b); if(a%b==0)return b; return gcd(b,a%b);}
//最小公倍数
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
//n乗の余り
ll modpow(ll x,ll n,ll mod){ll res=1;for(ll i=0;i<n;i++){res=res*x%mod;}return res;}
ll MODpow(ll x,ll n){ll res=1;for(ll i=0;i<n;i++){res=res*x%MOD;}return res;}


/*--------------------------------------------------------------------------*/

//main関数
int main() {
    char c; cin >> c;
    cout << char(c + 1) << endl;
}



Measured memory_bytes: 3572
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    vector<int> a(n,0);
    for(int i=0;i<n;i++)cin>>a[i];
    vector<bool> b(k+1,0);
    b[0]=false;
    for(int i=1;i<=k;i++){
        for(int j=0;j<n;j++){
            if(i-a[j]<0){
                b[i]=b[i] || false;
            }else{
                b[i]=!b[i-a[j]] || b[i];
            }
            
        }
    }
    if(b[k]==true){
        cout<<"First"<<endl;
    }else{
        cout<<"Second"<<endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long
#define mod 998244353
const int N=200005;



int main() {
	/*#ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("output.txt", "w", stdout);
	#endif
	*/
    cout<<fixed<<setprecision(15);


    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++) {
    	cin>>a[i];
    }
	sort(a,a+n);
	double sm=(a[0]+a[1])/2.0;
	for(int i=2;i<n;i++) {
		sm=(sm+a[i])/2;
	}
	cout<<sm;
	return 0;
}

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

using namespace std;

typedef long long lli;
typedef double lld;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<double> vdl;
typedef vector<vector<lli>> mat;
typedef vector<vdl> mad;
typedef unordered_map<lli,unordered_map<lli,lli>> graph;
typedef complex<double> cmp;
typedef vector<cmp> vcl;

const lli e5 = 1 << 20;
const lli mod = 1000000007;
const lli e3 = 1 << 13;
const lli INF = 1ll << 62;

lli h,w,d;
unordered_map<lli,lli> x;
unordered_map<lli,lli> y;
unordered_map<lli,lli> cost;
lli q;
lli l[e5],r[e5];

int main(){
  cin >> h >> w >> d;
  for(lli i = 1;i <= h;i++){
    for(lli j = 1;j <= w;j++){
      lli a;
      cin >> a;
      x[a] = i;
      y[a] = j;
    }
  }
  for(lli i = 1;i <= d;i++){
    for(lli j = i;j <= h*w;j += d){
      cost[j+d] = cost[j]+abs(x[j]-x[j+d])+abs(y[j]-y[j+d]);
    }
  }
  cin >> q;
  for(lli i = 0;i < q;i++){
    cin >> l[i] >> r[i];
  }
  for(lli i = 0;i < q;i++){
    cout << cost[r[i]]-cost[l[i]] << endl;
  }
}


Measured memory_bytes: 26164
if __name__ == "__main__":
    n = int(input())
    num = list(map(int,input().split()))
    # print(type(num[0]))
    cnt = 0
    for i in range(1,n+1):
        # print(i,num[i-1])
        if(num[i-1] % 2 != 0 and i % 2 != 0):
            cnt += 1
    print(cnt)

Measured memory_bytes: 8964
#include <iostream>
#include <utility>
#include <tuple>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <functional>
#include <climits>
#include <numeric>
#include <queue>
#include <cmath>
#include <iomanip>
#include <array>
#include <string>
#include <stack>
#include <cassert>
#include <memory>
constexpr int MOD = 1000000007;
bool is_odd(const int value) {
	return (value & 1) == 1;
}
bool is_match_xyz(const int value, const int x, const int y, const int z) {
	return is_odd(value >> (z - 1)) && is_odd(value >> (y + z - 1)) && is_odd(value >> (x + y + z - 1));
}
int last_count(const int value) {
	if (value == 0) return 0;
	return (value & 1) == 1 ? 1 : last_count(value >> 1) + 1;
}
long long int power(const long long int base, const int exp) {
	switch (exp) {
	case 0: return 1LL;
	case 1: return base % MOD;
	default: return power(base * base % MOD, exp >> 1) * power(base, exp & 1) % MOD;
	}
}
int main() {
	int n, x, y, z; std::cin >> n >> x >> y >> z;
	const auto length = std::max(10, x + y + z);
	std::vector<std::vector<long long int>> memo(n + 1, std::vector<long long int>(1 << length, 0));
	const auto mask = (1 << length) - 1;
	memo[0][0] = 1;
	for (auto i = 0; i < n; ++i) {
		for (auto j = 0; j < memo[i].size(); ++j) if (memo[i][j] != 0) {
			for (auto k = 0; k < 10; ++k) {
				const auto next = (j << (k + 1)) + (1 << k);
				if (!is_match_xyz(next, x, y, z)) {
					memo[i + 1][next & mask] += memo[i][j];
					memo[i + 1][next & mask] %= MOD;
				}
			}
		}
	}
	long long int result{ 0 };
	for (const auto s: memo.back()) {
		result += s;
		result %= MOD;
	}
	std::cout << (power(10, n) - result + MOD) % MOD << '\n';
}


Measured memory_bytes: 43392
import java.util.*;
import java.io.*;
import static java.lang.Math.*;

public class Main {
    static int n;
    static double[][][] dp;
    static boolean[][][] flg;
    public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		// 入力
		n = sc.nextInt();
		dp = new double[n+1][n+1][n+1];
		flg = new boolean[n+1][n+1][n+1];
		int[] a = new int[4];
		for(int i = 0; i < n; i++){
		    int tmp = sc.nextInt();
		    a[tmp]++;
		}
		
		// 計算
		double result = 0;
		flg[0][0][0] = true;
		result = func(a[1], a[2], a[3]);
		
		// 出力
		System.out.println(result);
	}
	
	public static double func(int x, int y, int z){
	    if(flg[x][y][z]) return dp[x][y][z];
	    flg[x][y][z] = true;
	    double A = 0;
	    double B = 0;
	    double C = 0;
	    if(x > 0) A = func(x-1, y, z)*x/n;
	    if(y > 0) B = func(x+1, y-1, z)*y/n;
	    if(z > 0) C = func(x, y+1, z-1)*z/n;
	    dp[x][y][z] = (A+B+C+1)*n/(x+y+z);
	    return dp[x][y][z];
	}

	public static class Scanner {
		private BufferedReader br; private StringTokenizer tok;
		public Scanner(InputStream is) throws IOException { br = new BufferedReader(new InputStreamReader(is));}
		private void getLine() throws IOException { while(!hasNext()) tok = new StringTokenizer(br.readLine());}
		private boolean hasNext() { return tok != null && tok.hasMoreTokens();}
		public String next() throws IOException { getLine(); return tok.nextToken();}
		public int nextInt() throws IOException { return Integer.parseInt(next());}
		public long nextLong() throws IOException { return Long.parseLong(next());}
		public double nextDouble() throws IOException { return Double.parseDouble(next());}
	}
}


Measured memory_bytes: 303764
#include<iostream>
#include<set>
#include<vector>
using namespace std;

int main(){
	int x,y;
	cin >> x >> y;
	int a[]{0,0,1,0,2,0,2,0,0,2,0,2,0};
	if(a[x] == a[y])cout << "Yes" <<endl;
	else cout << "No" << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,a,n) for(int i = (a); i < (n); ++i)
#define ALL(a) (a).begin(), (a).end()
#define debug_v(v,N) for(int i=0;i<N;i++) { cout << v[i] << " "; } cout << endl;
#define debug_vv(v,H,W) for(int i=0;i<H;i++) { for(int j=0;j<W;j++) { cout << v[i][j] << " "; } cout << endl; }

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;

void Main()
{
	int N, Q; cin >> N >> Q;
	vvi edges(N);
	rep(i, N - 1) {
		int a, b; cin >> a >> b;
		--a, --b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	vector<int> pq(N, 0);
	rep(i, Q) {
		int p, q; cin >> p >> q;
		pq[--p] += q;
	}
	vi cnt(N, 0);
	queue<int> q;
	q.push(0);
	vector<bool> use(N, false);
	while (!q.empty()) {
		int node = q.front(); q.pop();
		cnt[node] += pq[node];
		for (int next : edges[node]) {
			if (use[next]) continue;
			q.push(next);
			cnt[next] += cnt[node];
		}
		use[node] = true;
	}
	rep(i, N) {
		cout << cnt[i];
		if (i != N - 1) cout << " ";
	}
	cout << endl;
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
}


Measured memory_bytes: 16500
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007

long double probability_of_getting_more_heads(vector<long double> probability)
{ 
  int n = probability.size();
  
  vector< vector<long double> > probability_heads(n+1, vector<long double>(n+1,0.0));
  
  probability_heads[0][0] = 1.0;
  for(int i=1; i<=n; i++)
  {
    for(int j=0; j<=i; j++)
    {
      if(j==0)
        probability_heads[i][j] = probability_heads[i-1][j]*(1-probability[i-1]);
      else
      	probability_heads[i][j] = probability_heads[i-1][j-1]*probability[i-1] + 
        						probability_heads[i-1][j]*(1-probability[i-1]);
    
      //cout << i << " " << j << " " << probability_heads[i][j] << " " << probability[i-1] <<  endl;
    }
     
  }
  
  long double ans = 0.0;
  for(int i=n; i>n/2; i--)
    ans = ans + probability_heads[n][i]; 
  
  return ans;
}

int main()
{
  int n;
  cin >> n;
  
  vector<long double> probability(n,0);
  
  for(int i=0; i<n; i++)
  {
    cin >> probability[i];
    //cout << probability[i] << " " << i << endl;
  }
  cout << setprecision(10) << probability_of_getting_more_heads(probability) << endl;
  
  return 0;
}

Measured memory_bytes: 141184
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<stack>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
int n;
map<char,int> cnt;
char s[10];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)   cin>>s,cnt[s[0]]++;
    if(cnt.size()==3) puts("Three");
    else puts("Four");
}


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 a,b;
  cin >> a >> b;
  if(a<=8 && b<=8) cout << "Yay!" << endl;
  else cout << ":(" << endl;
  return 0;
}


Measured memory_bytes: 256
a, b, c, x, y = gets.chomp.split.map(&:to_i)
c *= 2 # A1枚B1枚のセットがC円とする

if c >= a + b
  puts a * x + b * y
elsif x == y
  puts c * x
else
  if x > y
    less_count = y
    rest_count = x - y
    many_pizza_price = a
  else
    less_count = x
    rest_count = y - x
    many_pizza_price = b
  end
  puts c * less_count + [many_pizza_price, c].min * rest_count
end


Measured memory_bytes: 1788
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3121000;
long long fact[C_SIZE];
long long finv[C_SIZE];
long long inv[C_SIZE];
long long Comb(int a,int b){
 	if(a<b||b<0)return 0;
 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
}
void init_C(int n){
	fact[0]=finv[0]=inv[1]=1;
	for(int i=2;i<n;i++){
		inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	}
	for(int i=1;i<n;i++){
		fact[i]=fact[i-1]*i%mod;
		finv[i]=finv[i-1]*inv[i]%mod;
	}
}
long long pw(long long a,long long b){
	long long ret=1;
	while(b){
		if(b%2)ret=ret*a%mod;
		a=a*a%mod;
		b/=2;
	}
	return ret;
}
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
double ABS(double a){return max(a,-a);}
// ここから編集しろ
int p[56000];
int cnt[31000];
int main(){
	int a;scanf("%d",&a);
	p[0]=p[1]=-1;
	for(int i=2;i<56000;i++){
		if(p[i]==0){
			p[i]=1;
			for(int j=i+i;j<56000;j+=i)p[j]=-1;
		}
	}
	int sz=0;
	for(int i=1;i<55555;i+=5){
		if(p[i]==1){
			cnt[sz++]=i;
		}
	}
	for(int i=0;i<a;i++){
		if(i)printf(" ");
		printf("%d",cnt[i]);
	}printf("\n");
}

Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_map>
using namespace std;
typedef long long ll;
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod
#define N 1000000
ll f(ll x,ll y){
    return abs(x-y*2);
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    ll n,x[200010];
    cin>>n;
    for(int i=0;i<n;i++)cin>>x[i];
    sort(x,x+n);
    ll best=-1e17;
    for(int i=0;i<n-1;i++){
	if(f(x[n-1],x[i])<f(x[n-1],best))best=x[i];
    }
    cout<<x[n-1]<<" "<<best<<endl;
}




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

#define int long long

int dfs(int r, int g, int b, int n);

int memo[305][305][305];
const int mod = 1e9 + 7;

struct data {
  int l, x;
};

vector < data > place[305];

main()
{

  memset(memo, -1, sizeof(memo));
  int n, m;
  
  cin >> n >> m;

  for(int p = 0; p < m; p++) {
    int l, r, x;
    cin >> l >> r >> x;
    place[r].push_back( (data) {l, x} );
  }
  
  cout << dfs(0, 0, 0, n) << endl;
  
  return (0);
}

int dfs(int r, int g, int b, int n)
{
  int pos = max(r, max(g, b));

  if(memo[r][g][b] != -1) return (memo[r][g][b]);
  
  vector < data > p = place[pos];
  if(p.size() > 0) {
    for(int i = 0; i < p.size(); i++) {
      int cnt = (p[i].l <= r) + (p[i].l <= g) + (p[i].l <= b);
      if(cnt != p[i].x) return memo[r][g][b] = (0);
    }
  }
  
  
  if(pos == n) return 1;
  
  int npos = pos + 1;
  
  return memo[r][g][b] = ((dfs(npos, g, b, n) + dfs(r, npos, b, n) + dfs(r, g, npos, n)) % mod);
}


Measured memory_bytes: 221952
#include<iostream>
#include<cctype>
#include<cstdio>
#include<cstring>
using namespace std;

string align(string a){
    string b = a;
    for(int i = 0; i < a.size(); i++){
        b[i] = tolower(a[i]);
    }
    return b;
}


int main(){
    int cou;
    string W, T;
    cin >> T;
    T = align(T);
    cou = 0;
    while(1){
        cin >> W;
        if(W == "END_OF_TEXT")break;
        W = align(W);
        if(T == W)cou++;
    }
    cout << cou << endl;
    return 0;
}


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

typedef long long ll;

#define SIZE_OF_ARRAY(array) (sizeof(array) / sizeof(array[0]))
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define AA(i) cout << i << endl;
#define AS(i) cout << i << " ";

const int INF = 1001001001;

const double PI = 3.14159;

using namespace std;

vector<ll> memo(1000007, INF);

int main() {

    int x;
    cin >> x;

    int ans = 1;
    if (x / 100 * 5 < x % 100)
        ans = 0;

    AA(ans);
}

Measured memory_bytes: 8064
# https://atcoder.jp/contests/abc047/tasks/arc063_a
import sys
sys.setrecursionlimit(12345678)
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def main():
    s = input()
    if len(s) == 0 or s.count('W') == 0 or s.count('B') == 0:
        print(0)
        return

    pre = s[0]

    ans = 0
    for i in range(1, len(s)):
        if pre != s[i]:
            ans += 1
        pre = s[i]
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 39280
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#define ll long long
#define rep(i, a, b) for(int i = a; i <= (int)b; i++)
void read(int &x) {
    x = 0; int flag = 1; char ch = ' ';
    while(ch < '0' || ch > '9') { if(ch == '-') flag = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    x *= flag;
}
void read(ll &x) {
    x = 0; int flag = 1; char ch = ' ';
    while(ch < '0' || ch > '9') { if(ch == '-') flag = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    x *= flag;
}
using namespace std;
int main()
{
	int n, a, b;
    read(n), read(a), read(b);
	cout << min(n * a, b);
    return 0;
}

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

#define MAX 1000000
#define INF 200000000
#define MOD 1000000007

typedef long long ll;
typedef unsigned long long llu;

using namespace std;

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

void IO()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
}

int arr[15];

bool cmp(int a, int b)
{
    return a>b;
}

int main()
{
    //IO();
    for(int i=0;i<10;i++)scanf("%d",&arr[i]);
    sort(arr,arr+10,cmp);
    for(int i=0;i<3;i++)printf("%d\n",arr[i]);
    return 0;
}

Measured memory_bytes: 3212
use std::cmp::min;
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("filed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n:usize = read();
    let mut ans = n - 1;
    for i in 2..=n {
        if i * i > n {
            break;
        }
        if n % i == 0 {
            ans = min(ans, i + n / i - 2);
        }
    }
    println!("{}", ans);
}


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

using namespace std;
typedef long long int ll;
/*bool compx(vector<ll> a, vector<ll> b)
{
    if(a[0]>=b[0])
        return false;
    else
        return true;
}*/

int main()
{   
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll h, n;
    cin>>h>>n;
    ll a[n], sum=0;
    for(ll i=0; i<n; i++)
    {
        cin>>a[i];
        sum+=a[i];
    }
    if(sum<h)
        cout<<"No";
    else
        cout<<"Yes";
    return 0;
}

Measured memory_bytes: 1024
#define _CRT_SECURE_CPP_OVERLOAD_SECURE_NAMES 1

#include <sstream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <random>
#include <ctime>

const long long INF = 10000000000000000;

using namespace std;



int main(){
	int sx,sy,tx,ty;
	cin>>sx>>sy>>tx>>ty;

	for(int i=0;i<tx-sx;i++) cout<<"R";
	for(int i=0;i<ty-sy;i++) cout<<"U";
	for(int i=0;i<tx-sx;i++) cout<<"L";
	for(int i=0;i<ty-sy;i++) cout<<"D";

	cout<<"D";

	for(int i=0;i<tx-sx+1;i++) cout<<"R";
	for(int i=0;i<ty-sy+1;i++) cout<<"U";
	cout<<"L";
	cout<<"U";
	for(int i=0;i<tx-sx+1;i++) cout<<"L";
	for(int i=0;i<ty-sy+1;i++) cout<<"D";
	cout<<"R"<<endl;
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FI first
#define SE second
#define PB push_back
#define ll long long
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
#define co(i) cout<<(i)<<endl
#define fcout cout<<fixed<<setprecision(10)
#define uni(i) i.erase(unique(i.begin(), i.end()), i.end());
#define all(i) i.begin(),i.end()
using namespace std;

const int INF=1e9+7;
const int MOD=1e9+7;

int main(){
    int a,b; cin>>a>>b;
    co((a-1)*(b-1));
}


Measured memory_bytes: 768
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <set>
#define rep(i, n) for(int i=0; i<n; i++)
#define repr(i, n) for(int i=n; i>=0; i--)
#define reps(i, s, e) for(int i=s; i<e; i++)
#define inf 1e10
#define vsort(v) sort(v.begin(), v.end())
#define vsortr(v) sort(v.begin(), v.end(), greater<lli>())
#define sz(x) x.size()
#define ceil(a, b) (a+b-1)/b
#define ok cout << "ok" << endl;
using namespace std;
using lli = long long int;
template<typename T> bool chmax(T &a, T &b){ if(a<b) { a=b; return 1; }}
template<typename T> bool chmin(T &a, T &b){ if(b<a) { a=b; return 1; }}
template<typename T> T gcd(T a, T b){ if(b==0) return a; return gcd(b, a%b); }
template<typename T> T lcm(T a, T b){ return a*b/gcd(a, b); }
template<typename T> T vdebug(vector<T> v){ for(auto vv : v){ cout << vv << " "; } cout << endl; }
template<typename T> T arrdebug(T arr[], int n){ rep(i, n){ cout << arr[i] << " "; } cout << endl; }
void ans(bool b){ if(b) cout << "Yes" << endl; else cout << "No" << endl; }
void ans2(bool b){ if(b) cout << "YES" << endl; else cout << "NO" << endl; }
int dx[] = {1, -1, 0, 0, 1, -1, 1, -1};
int dy[] = {0, 0, 1, -1, 1, -1, -1, 1};


int main(){
	int n, tmph;
	vector<int> h;
	cin >> n;
	rep(i, n){
		cin >> tmph;
		h.push_back(tmph);
	}
	
	int dp[100001];
	rep(i, n){
		dp[i] = inf;
	}
	dp[0] = 0;		

	rep(i, n-1){
		if(i==0) dp[i+1] = abs(h[i+1] - h[i]);
		else dp[i+1] = min(dp[i] + abs(h[i+1]-h[i]), dp[i-1] + abs(h[i+1]-h[i-1]));
	}
	
	cout << dp[n-1] << endl;
	return 0;
}


Measured memory_bytes: 1144
n = int(input())
A = list(map(int, input().split()))

A.sort()
from itertools import accumulate
C = [0]+A
C = list(accumulate(C))

def is_ok(x):
    if x == n-1:
        return True
    y = C[x+1]
    flag = True
    for i in range(x+1, n):
        if A[i] > 2*y:
            flag = False
        y += A[i]
    if flag:
        return True
    else:
        return False

if is_ok(0):
    print(n)
    exit()

l = 0
r = n-1
while l+1 < r:
    c = (l+r)//2
    if is_ok(c):
        r = c
    else:
        l = c
print(n-r)


Measured memory_bytes: 65256
N, M = map(int, input().split())

ac = [0] * N
wa = [0] * N

for i in range(M):
    p,s = input().split()
    p = int(p)
    p -= 1
    if ac[p]:
        continue
    if s == 'AC': 
        ac[p] = 1
    else:
        wa[p] += 1
AC = sum(ac)
WA = 0
for i in range(N):
    if ac[i]:
        WA += wa[i]
print(AC, WA)

Measured memory_bytes: 4596
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; ++i)
#define REPP(i, n) for(int i = 1; i <= n; ++i)
#define REPR(i, n) for(int i = n-1; i >= 0; --i)
#define FOR(i, m, n) for(int i = m; i < n; ++i)
#define ALL(v) v.begin(), v.end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1000000007;
const ll INF = 1000000000;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h,w; cin >> h >> w;
    vector<string> a(h);
    REP(i,h) cin >> a[i];
    bool ans = true;
    [&] {
        REP(i,h) {
            REP(j,w) {
                if(a[i][j]=='#') {
                    if(i<h-1 && j<w-1) ans = ((a[i+1][j]=='#' && a[i][j+1]=='.') || (a[i][j+1]=='#' && a[i+1][j]=='.'));
                    if(i>0 && j>0) ans = !(a[i-1][j]=='#' && a[i][j-1]=='#');
                }
                if(!ans) return;
            }
        }
    }();
    cout << (ans ? "Possible" : "Impossible") << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int a[2000005];
int main()
{
    /*int x;
    cin >> x;
    if(x>=400&&x<=599)
        cout << 8 << endl;
    if(x>=600&&x<=799)
        cout << 7 << endl;
    if(x>=800&&x<=999)
        cout << 6 << endl;
    if(x>=1000&&x<=1199)
        cout << 5 << endl;
    if(x>=1200&&x<=1399)
        cout << 4 << endl;
    if(x>=1400&&x<=1599)
        cout << 3 << endl;
    if(x>=1600&&x<=1799)
        cout << 2 << endl;
    if(x>=1800&&x<=1999)
        cout << 1 << endl;*/
    /*int  a,b,c,k;
    cin >> a>> b >> c >> k;
    while(k&&b<=a)
    {
        b = b*2;
        k--;
    }
    while(k&&c<=b)
    {
        c = c*2;
        k--;
    }

    if(b>a&&c>b)
        cout << "Yes\n";
    else
    cout << "No\n";*/
    int n,k;
    cin >> n >> k;
    int cur=1;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
    }
    for(int i=k+1;i<=n;i++)
    {
        if(a[i]>a[cur++])
            cout << "Yes\n";
        else

            cout << "No\n";
    }
}


Measured memory_bytes: 4416
N = int(input())
def main():
    a = list(map(int, input().split()))
    d = {0:0, 1:0, 2:0, 3:0}
    for i in a:
        d[i] += 1
    d1 = d[1]
    d123 = d[1] + d[2] + d[3]
    d23 = d[2] + d[3]
    d3 = d[3]
    d2 = d[2]
    l = [[[0] * (d123 + 1) for _ in range(d23 + 1)] for _ in range(d3 + 1)]
    for i in range(d3 + 1):
        for j in range(d23 + 1):
            for k in range(d123 + 1):
                if i + j + k == 0:
                    continue
                if i + j + k > d123:
                    continue
                if i + j > d23:
                    continue
                total = i + j + k
                a = b = c = 0
                if k > 0:
                    a = k * l[i][j][k-1]
                if j > 0:
                    b = j * l[i][j-1][k + 1]
                if i > 0:
                    c = i * l[i-1][j + 1][k]
                l[i][j][k] = (a + b + c + N)/total
    print(l[d3][d2][d1])
main()



Measured memory_bytes: 496136
using System;
using System.Collections.Generic;
using System.Dynamic;
using System.Linq;

namespace atcorder
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            if(N % 2 == 0)
            {
                Console.WriteLine(N / 2);
            }
            else
            {
                Console.WriteLine(N / 2 + 1);
            }
        }
    }
}

//文字配列の取得
//string[] strArray = Console.ReadLine().Split(' ').ToArray();
//string S = strArray[0];
//string T = strArray[1];

//文字列の取得
//string s = Console.ReadLine();

//数字配列の取得
//int[] intArray = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
//int H = intArray[0];
//int W = intArray[1];

//数字の取得
//int N = int.Parse(Console.ReadLine());

//リスト型(int)の取得
//List<int> A = new List<int>(Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray());

//出力
//Console.WriteLine(ans);
//Console.WriteLine("Yes");
//Console.WriteLine("No");
//Console.WriteLine(cnt);



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


int main(){
    string s;
    cin >> s;
    int n = s.size();
    string s_i = "";
    int counter = 0;
    int ans = 0;
    while(counter<n){
        if(counter == n-1 && s_i==s.substr(counter,1)) break;
        if(s_i==s.substr(counter,1)){
            s_i=s.substr(counter,2);
            ans ++;
            counter +=2;
        }
        else{
            s_i=s.substr(counter,1);
            ans ++;
            counter ++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 640
# coding=UTF-8
from collections import deque
from operator import itemgetter
from bisect import bisect_left, bisect
import itertools
import sys
import math
import numpy as np
import time
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


def main():
    k = int(input())
    flag = 0
    a, b = map(int, input().split())
    for i in range(a, b + 1):
        if i % k == 0:
            print("OK")
            flag = 1
            break
    if flag == 0:
        print("NG")


if __name__ == '__main__':
    main()


Measured memory_bytes: 27144
n,l = map(int,input().split())
lst=[]
for i in range(1,n+1):
    lst.append(l+i-1)

if min(lst)>0:
    ans=sum(lst)-min(lst)
elif max(lst)<0:
    ans=sum(lst)-max(lst)
else:  
    m = abs(lst[0])
    for i in range(n):
        if abs(lst[i])<m:
            m=abs(lst[i])
    ans=sum(lst)-m
print(ans)

Measured memory_bytes: 3064
D=int(input())
C=list(map(int,input().split()))
S=[list(map(int,input().split())) for i in range(D)]
T=0
X=[0]*26
P=0
for i in range(D):
  T=int(input())
  P+=S[i][T-1]
  for j in range(26):
    X[j]+=C[j]
  X[T-1]=0
  P-=sum(X)
  print(P)

Measured memory_bytes: 9388
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <numeric>

using namespace std;

int main(){

  int x, a, b;
  cin >> x >> a >> b;
  x = x - a;
  cout << x - ((x / b) * b) << endl;

  return 0;
}


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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

using i64=int64_t;

i64 f(i64 b,i64 n){
    if(n<b) return n;
    return f(b,n/b)+n%b;
}

void solve(){
    i64 n,s;
    cin >> n >> s;

    if(s>n){
        cout << -1 << endl;
        return;
    }

    if(n==s){
        cout << n+1 << endl;
        return;
    }
    
    for(i64 b=2; b*b<=n; ++b){
        if(f(b,n)==s){
            cout << b << endl;
            return;
        }
    }

    i64 ans=-1;
    for(i64 p=1; p*p<n; ++p){
        i64 b=(n-s)/p+1;
        if(b>=2 and f(b,n)==s) ans=b;
    }
    cout << ans << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    solve();
    return 0;
}


Measured memory_bytes: 256
from collections import Counter

N,*A = map(int,open(0).read().split())
#j - i = Aj + Ai
#j - Aj = Ai + i
#L = i + Ai, R = j - Aj とおく
L = []
R = []
for i in range(N):
    L.append(i+1 + A[i])
    R.append(i+1 - A[i])
l = Counter(L)
r = Counter(R)
 
cnt = 0
a = []
for i in range(1,N+1):
    if i in l and i in r:
        cnt += l[i] * r[i]
        a.append(i)
print(cnt)

Measured memory_bytes: 150040
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    if (a < b)
    {
        if (b < c)
        {
            cout << "Yes" << endl;
        }
        else
            cout << "No" << endl;
    }
    else
        cout << "No" << endl;
}


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

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

    ll a, b, c, k;
    cin >> a >> b >> c >> k;

    ll res = a-b;

    if(k%2) cout << -res << endl;
    else cout << res << endl;

    return 0;
}

Measured memory_bytes: 384
import java.util.Scanner;

public class Main{
   
    
    public static void main(String[] args){
        int n;
        int[] R;
        
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        R = new int[n];
  
        for( int i = 0; i < n; i++) R[i] = sc.nextInt();
        
        int a = R[1] - R[0];
        int m = R[0];
        for ( int i = 1; i < n; i++){
            if (R[i] - m > a ) a = R[i] - m;
            if (R[i] < m ) m = R[i];
    }
    System.out.println(a);
  
    }
}

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

int a[55];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    int sum = 0;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            sum += a[i]*a[j];
        }
    }
    cout << sum << endl;
    return 0;
}

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

#define rep(i,n) for(int i=0;i<(n);i++)
#define INT(n) int n;scanf("%d",&n);
#define LL(n) long long n;scanf("%lld",&n);
#define pint(n) printf("%d",n);
#define pll(n) printf("%lld",n);
#define psp printf(" ");
#define pln puts("");

int main(){
	LL(Q)
	LL(H)
	LL(S)
	LL(D)
	LL(N)
	long long cost1=Q*4;
	cost1 = std::min<long long>(cost1,H*2);
	cost1 = std::min<long long>(cost1,S);
	long long cost2 = std::min<long long>(cost1*2,D);
	unsigned long long ans=0;
	ans += (N-N%2)/2*cost2;
	ans += (N%2)*cost1;
	printf("%lld",ans);
	pln
	return 0;
}

Measured memory_bytes: 256
H,W=map(int,input().split())
S=[list(input()) for i in range(H)]

for i in range(H):
  for j in range(W):
    if S[i][j]=='#':
      flg = 0
      flg += 1 if i-1>=0 and S[i-1][j]=='#' else 0
      flg += 1 if i+1<H and S[i+1][j]=='#' else 0
      flg += 1 if j-1>=0 and S[i][j-1]=='#' else 0
      flg += 1 if j+1<W and S[i][j+1]=='#' else 0
      if flg==0:
        print('No')
        exit(0)
print('Yes')

Measured memory_bytes: 3064
#include<iostream>
using namespace std;
int main(void){

  double in;
  while(cin >> in!='\0'){
    if(in>91.00)
      cout << "heavy" << endl;
    else if(in>81.00)
      cout << "light heavy" << endl;
    else if(in>75.00)
      cout << "middle" << endl;
    else if(in>69.00)
      cout << "light middle" << endl;
    else if(in>64.00)
      cout << "welter" << endl;
    else if(in>60.00)
      cout << "light welter" << endl;
    else if(in>57.00)
      cout << "light" << endl;
    else if(in>54.00)
      cout << "feather" << endl;
    else if(in>51.00)
      cout << "bantam" << endl;
    else if(in>48.00)
      cout << "fly" << endl;
    else
      cout << "light fly" << endl;


  }

}

Measured memory_bytes: 1220
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define ll long long
using namespace std;
//typedef vector<unsigned int>vec;
//typedef vector<ll>vec;
//typedef vector<vec> mat;
typedef pair<int, int> P;
typedef pair<ll,ll> LP;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int INF = 1000000000;
const ll LINF = 1000000000000000000;//1e18
const ll  MOD = 1000000007;
const double PI = acos(-1.0);
const double EPS = 1e-10;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
//template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};



int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, K;
    cin >> N >> K;
    N %= K;
    cout << min(N, abs(N - K)) << endl;
}

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

using namespace std;

int main() {
    int n; cin >> n;
    string s; cin >> s;
    vector<int> easter(n + 1);
    vector<int> wester(n + 1);
    for(int i = 1; i < n + 1; ++i){
        if(s[i - 1] == 'W') wester[i] = wester[i - 1] + 1;
        else wester[i] = wester[i - 1];
    }
    for(int i = n - 1; i >= 0; --i) {
        if (s[i] == 'E') easter[i] = easter[i + 1] + 1;
        else easter[i] = easter[i + 1];
    }
    int ans = 1 << 29;
    for(int i = 0; i < n; ++i){
        int wronger = wester[i] + easter[i + 1];
        ans = min(ans, wronger);
    }

    cout << ans  << endl;
    return 0;

}

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

int main()
{
    int K,X;
    cin >> K >> X ;

    if(500*K>=X){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;

}

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

using namespace std;

int main()
{
	unsigned short maxheight[10] = {0};
	for (int i = 0; i < 10; i++)
		cin >> maxheight[i];
	sort(maxheight, maxheight + 10);
	for (int i = 0; i < 3; i++)
		cout << maxheight[9-i] << endl;
	return 0;
}


Measured memory_bytes: 3080
N,M = map(int,input().split())

from collections import deque
ls = [deque([]) for _ in range(N)]

for i in range(M):
    a,b,c = map(int,input().split())
    a,b = a-1,b-1
    ls[a].append([b,c])
cost = [-(10**10)*N]*N
cost[0] = 0

for i in range(N):
    update = False
    q = [deque(m for m in l) for l in ls]
    for j in range(N):
        if cost[j] != -(10**10)*N:
            while q[j]:
                b,c = q[j].pop()
                if cost[b] < cost[j] + c:
                    cost[b] = cost[j] + c
                    update = True
    if i == 0:
        Max = cost[N-1]
    elif i < N-1:
        Max = max(Max,cost[N-1])

if update == True and Max < cost[N-1]:
    print('inf')
else:
    print(Max)


Measured memory_bytes: 5612
# -*- coding: utf-8 -*-
def main():
    N = int(input())
    H = list(map(int,input().split()))
    H.reverse()
    for i in range(N):
        if i != N-1:
            if H[i]>=H[i+1]:
                continue
            if (H[i+1]-H[i])==1:
                H[i+1]=H[i+1]-1
            else:
                print('No')
                return
    if H[N-1]<=H[N-2] or (H[N-1]-H[N-2]==1):
        print('Yes')
        return
    else:
        print('No')
        return

if __name__ == '__main__':
    main()

Measured memory_bytes: 14396
#include <stdio.h>
#define INF 1000000
#define white 0
#define black 2
#define gray 1

int n,M[100][100];

void dijkstra();

int main(){
  int i,j,k,c,v,u;
  scanf("%d",&n);
  for(i=0;i<n;i++){ 
    for(j=0;j<n;j++){
      M[i][j]=INF;
    }
  }
  for(i=0;i<n;i++){
    scanf("%d%d",&u,&k);
    for(j=0;j<k;j++){
      scanf("%d%d",&v,&c);
      M[u][v]=c;
    }
  }
  dijkstra();
  
  return 0;
}
void dijkstra(){
  int i,d[100],mincost,color[100],v,u;
  for(i=0;i<n;i++){
    d[i]=INF;
    color[i]=white;
  }
  d[0]=0;
  color[0]=gray;

  while(1){
    mincost=INF;
    u=-1;
    for(i=0;i<n;i++){
      if(color[i]!=black&&d[i]<mincost){
	mincost=d[i];
	u=i;
      }
    }
    if(u==-1)break;
    
    color[u]=black;
    for(v=0;v<n;v++){
      if(color[v]!=black&&M[u][v]!=INF){
	if(d[v]>d[u]+M[u][v]){
	  d[v]=d[u]+M[u][v];
	  color[v]=gray;
	}
      }
    }
  }
  for(i=0;i<n;i++){
    printf("%d ",i);
    if(d[i]==INF)printf("-1");
    else printf("%d",d[i]);
    printf("\n");
  }
}



Measured memory_bytes: 2004
//In the name of GOD
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll maxn = 2e5 + 100;
const ll maxm = 1e6 + 100;
const ll mod = 1e9 + 7;
const ll inf = 1e18;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt" , "r+" , stdin) ; freopen("output.txt" , "w+" , stdout);
#define pb push_back
#define Mp make_pair
#define pll pair<ll, ll>
#define F first
#define S second

ll n, m, t, d[maxm];
bool vis[maxm];
pair<pll, ll> e[maxn];
vector<ll> g[maxm], p[maxn], dsu[maxm], sz[maxm];
map<ll, ll> mp[maxn];
queue<ll> q;

ll root(ll c, ll v){
	if(dsu[c][v] != v) dsu[c][v] = root(c, dsu[c][v]);
	return dsu[c][v];
}

void Union(ll c, ll v, ll u){
	v = root(c, v);
	u = root(c, u);
	if(v == u) return;
	if(sz[c][v] < sz[c][u]) swap(v, u);
	dsu[c][u] = v;
	sz[c][v] += sz[c][u];
	return;
}

int main(){
	ll v, u, c;
	fast_io;
	
	cin >> n >> m;
	for(ll i = 0; i < m; i++){
		cin >> v >> u >> c;
		p[v].pb(c);
		p[u].pb(c);
		if(mp[v][c] == 0){
			dsu[c].pb(dsu[c].size());
			sz[c].pb(1);
			mp[v][c] = dsu[c].size();
		}
		if(mp[u][c] == 0){
			dsu[c].pb(dsu[c].size());
			sz[c].pb(1);
			mp[u][c] = dsu[c].size();
		}
		e[i] = Mp(Mp(v, u), c);
	}
	for(ll i = 0; i < m; i++){
		v = e[i].F.F;
		u = e[i].F.S;
		c = e[i].S;
		Union(c, mp[v][c] - 1, mp[u][c] - 1);
	}
	t = n + 1;
	for(ll i = 1; i < maxm; i++){
		for(ll j = 0; j < dsu[i].size(); j++){
			if(dsu[i][j] == j) sz[i][j] = t++;
		}
	}
	for(ll i = 1; i <= n; i++){
		for(ll j = 0; j < p[i].size(); j++){
			g[i].pb(sz[p[i][j]][root(p[i][j], mp[i][p[i][j]] - 1ll)]);
			g[sz[p[i][j]][root(p[i][j], mp[i][p[i][j]] - 1ll)]].pb(i);
		}
	}
	q.push(1);
	vis[1] = 1;
	while(!q.empty()){
		v = q.front();
		q.pop();
		for(ll i = 0; i < g[v].size(); i++){
			u = g[v][i];
			if(!vis[u]){
				vis[u] = 1;
				d[u] = d[v] + 1;
				q.push(u);
			}
		}
	}
	if(!vis[n]) cout << -1;
	else cout << d[n] / 2;
	
	return 0;
}


Measured memory_bytes: 149504
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const ll INF = 10e9;
int main(){
  int n;
  cin >> n;
  vector<vector<int>> abc(n,vector<int>(3));
  for(int i=0;i<n;i++){
    for(int j=0;j<3;j++){
      cin >> abc[i][j];
    }
  }

  vector<vector<ll>> dp(n,vector<ll>(3));

  //dpテーブルの初期化
  for(int i=0;i<n;i++){
    for(int j=0;j<3;j++){
      dp[i][j] = 0;
    }
  }

  //初期値代入
  for(int j=0;j<3;j++){
    dp[0][j] = abc[0][j];
  }

  for(int i=1;i<n;i++){
    for(int j=0;j<3;j++){
      for(int k=0;k<3;k++){
        if(j==k) continue;

        dp[i][j] = max(dp[i][j],dp[i-1][k]+abc[i][j]);

      }
    }
  }

  cout << max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2])) << endl;
}


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

#define int long long
#define pb push_back
#define mp make_pair
#define f(i,a,n) for(int i=a ; i<n ; i++)
#define all(c) (c).begin(),(c).end()
#define F first
#define S second
#define fast ios:: sync_with_stdio(false),cin.tie(nullptr);
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef vector<pii> vpi;

const int inf = 1e9;
const int inf64 = 1e18;
const int MOD = inf + 7;
const ld PI = acos(-1.0);

int32_t main(){
	fast;
	int n;
	cin >> n;
	
	vector<int>a(n) , b(n);
	f(i,0,n)    cin >> a[i];
	f(i,0,n)    cin >> b[i];
	
	vector<int> c(n);
	f(i,0,n)    c[i] = i+1;
	int cnt = 1;
	int ans = 0;
	do
	{
		if(c == a)
		 ans += cnt ;
		if(c == b)
		 ans -= cnt;
		cnt++;
	}
	while(next_permutation(all(c)));
	
	cout << abs(ans);
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef vi poly;

template<class T> inline void read(T &x){
	int f=0;x=0;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())f|=(ch=='-');
	for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
	if(f)x=-x;
}

const int mod=998244353;
const int N=(1<<14)+5,G=3;
inline int power(int x,int p){
	int res=1;
	for(;p;x=1ll*x*x%mod,p>>=1)
		if(p&1)res=1ll*res*x%mod;
	return res;
}
inline const int fix(const int x){
	return x>=mod?x-mod:x;
}
void dft(int *A,int n){
	static ull W[N<<1],*H[30],*las=W,mx=0;
	for(;mx<n;mx++){
		H[mx]=las;ull w=1,wn=power(G,(mod-1)>>(mx+1));
		REP(i,1<<mx)*las++=w,w=w*wn%mod;
	}
	static ull a[N];
	for(int i=0,j=0;i<(1<<n);++i){
		a[i]=A[j];
		for(int k=1<<(n-1);(j^=k)<k;k>>=1);
	}
	ull tmp,*l=a,*r=a+1;
	for(int i=0;i<(1<<n);i+=2,++l,++r)
		tmp=*r,*r=*l+mod-tmp,*l+=tmp,++l,++r;
	for(int k=1,d=2;k<n;k++,d<<=1)
		for(int i=0;i<(1<<n);i+=d<<1){
			ull *l=a+i,*r=a+i+d,*w=H[k],t;
			for(int j=0;j<d;j+=2,l+=2,r+=2){
				t=(*w++)*(*r)%mod;
				*r=*l+mod-t,*l+=t;
				t=(*w++)*(*(r+1))%mod;
				*(r+1)=*(l+1)+mod-t,*(l+1)+=t;
			}
		}
	REP(i,1<<n)A[i]=a[i]%mod;
}
void idft(int *a,int n){
	reverse(a+1,a+(1<<n));
	dft(a,n);ll inv=power(1<<n,mod-2);
	REP(i,1<<n)a[i]=1ll*a[i]*inv%mod;
}

int fac[N],rev[N],f[N],g[N];
int n,m,k;

void init(int n){
	fac[0]=1;
	rep(i,1,n)fac[i]=(ll)fac[i-1]*i%mod;
	rev[n]=power(fac[n],mod-2);
	per(i,n,1)rev[i-1]=(ll)rev[i]*i%mod;
}

int A[N],B[N];

int main(){
	read(m),read(n),init(m+2);
	rep(i,0,m)f[i]=(ll)fac[m]*rev[i]%mod*rev[m-i]%mod;
	while((1<<k)<2*m)k++;
	rep(j,1,m)B[m-j]=rev[j+2];
	dft(B,k);
	per(i,n,1){
		rep(j,1,m)A[j]=(ll)fac[j+2]*f[j]%mod;
		rep(j,m+1,(1<<k)-1)A[j]=0;
		dft(A,k);
		REP(j,1<<k)A[j]=(ll)A[j]*B[j]%mod;
		idft(A,k);
		rep(j,0,m)g[j]=((ll)A[m+j]*rev[j]+((ll)j*(j+1)/2+1)%mod*f[j])%mod;
		swap(f,g);
	}
	printf("%d\n",f[0]);
	return 0;
}

Measured memory_bytes: 768
#![allow(unused_imports)]
#![allow(unused_variables)]
use proconio::input;
use proconio::marker::*;
use std::cmp::{min, max};
use std::collections::{HashSet, HashMap, BinaryHeap};

fn main() {
    input! {
        a: u64,
        b: f64,
    }
    let ans = (a * ((b * 100.0).round()) as u64) / 100;
    println!("{}", ans);
}


Measured memory_bytes: 2608
#include <algorithm>
#include <cmath>
#include <iostream>
#include <deque>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#include <unordered_map>
#include <unordered_set>

using namespace std;

int main()
{
	string str;
	cin >> str;

	if ("SUN" == str)
	{
		cout << 7 << endl;
	}
	else if ("MON" == str)
	{
		cout << 6 << endl;
	}
	else if ("TUE" == str)
	{
		cout << 5 << endl;
	}
	else if ("WED" == str)
	{
		cout << 4 << endl;
	}
	else if ("THU" == str)
	{
		cout << 3 << endl;
	}
	else if ("FRI" == str)
	{
		cout << 2 << endl;
	}
	else if ("SAT" == str)
	{
		cout << 1 << endl;
	}
}

Measured memory_bytes: 256