akhauriyash/Code-Regression huggingface dataset:
//	Mohib Manva
#include<bits/stdc++.h>
using namespace std;

#define mod 1000000007
#define LOCAL 0
#define pb push_back
#define ll long long

ll po(ll a,ll b){
	ll x = 1,y=a;
	while(b>0){
		if(b%2){
			x = x*y;
			x %= mod;
		}
		y=y*y;
		y%=mod;
		b/=2;
	}
	return x;
}

const int maxnodes = 505;

long long int nodes = maxnodes, src, dest;
long long int dist[maxnodes], q[maxnodes], work[maxnodes];

struct Edge {
  int to, rev;
  long long int f, cap;
};

vector<Edge> g[maxnodes];


//	biderectional edges.
void addEdgeUndirected(int s, int t, long long int cap){
  Edge a = {t, g[t].size(), 0ll, cap};
  Edge b = {s, g[s].size(), 0ll, cap};
  g[s].push_back(a);
  g[t].push_back(b);
}

//	unidirectional edges.
void addEdgeDirected(int s, int t,long long int cap){
  Edge a = {t, g[t].size(), 0ll, cap};
  Edge b = {s, g[s].size(), cap, cap};
  g[s].push_back(a);
  g[t].push_back(b);
}

bool dinic_bfs() {
  //fill(dist, dist + nodes, -1);
  for(int i=0;i<nodes;i++)	dist[i] = -1;
  dist[src] = 0;
  int qt = 0;
  q[qt++] = src;
  for (int qh = 0; qh < qt; qh++) {
    int u = q[qh];
    for (int j = 0; j < (int) g[u].size(); j++) {
      Edge &e = g[u][j];
      int v = e.to;
      if (dist[v] < 0 && e.f < e.cap) {
        dist[v] = dist[u] + 1;
        q[qt++] = v;
      }
    }
  }
  return dist[dest] >= 0;
}

long long dinic_dfs(int u,long long int f) {
  if (u == dest)
    return f;
  for (ll &i = work[u]; i < (int) g[u].size(); i++) {
    Edge &e = g[u][i];
    if (e.cap <= e.f) continue;
    int v = e.to;
    if (dist[v] == dist[u] + 1) {
      int df = dinic_dfs(v, min(f, e.cap - e.f));
      if (df > 0) {
        e.f += df;
        g[v][e.rev].f -= df;
        return df;
      }
    }
  }
  return 0ll;
}

long long maxFlow(int _src, int _dest) {
  src = _src;
  dest = _dest;
  long long int result = 0;
  while (dinic_bfs()) {
    for(int i=0;i<nodes;i++){
    	work[i] = 0;
    }
    //fill(work, work + nodes, 0);
    while (int delta = dinic_dfs(src, INT_MAX))
      result += delta;
  }
  return result;
}

int main(){
	if(LOCAL){
    	freopen("C:/Users/gold/Desktop/sublime IO/input.txt","r",stdin);
    	freopen("C:/Users/gold/Desktop/sublime IO/output.txt","w",stdout);
	}
	int T = 1;
	//scanf("%d",&T);
	while(T--){
		int n;
		scanf("%d",&n);
		static ll a[555];
		for(int i=1;i<=n;i++){
			scanf("%lld",&a[i]);
		}		
		
		for(int i=1;i<=n;i++){
			for(int j=i;j<=n;j+=i){
				addEdgeDirected(i,j,INT_MAX);
			}
		}

		int src = 0,dest = n + 1;
		ll tot = 0ll;
		for(int i=1;i<=n;i++){
			if(a[i] <= 0){
				addEdgeDirected(src,i,-a[i]);
			} else {
				addEdgeDirected(i,dest,a[i]);
				tot += a[i];
			}
		}
		printf("%lld\n",tot-maxFlow(src,dest));
		//printf("%lld\n",tot + max(0,maxFlow(src,dest)));
	}
	return 0;	
}

Measured memory_bytes: 256
use std::vec::Vec;

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

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


fn main() {
    let s: Vec<char> = read::<String>().chars().collect();
    let n: usize = s.len();
    // 左端から見たときのRLの距離
    let mut posit = vec![0; n];
    let mut dist: Vec<(char, usize)> = vec![('x', std::usize::MAX); n];
    let mut ans: Vec<usize> = vec![0; n];
    // 0 -> 意味なし
    // 1 -> R
    // 2 -> L
    for i in 0..n-1 {
      if s[i] == 'R' && s[i+1] == 'L' {
        posit[i] = 1;
        posit[i+1] = 2;
      }
    }

    for i in 0..n {
      if s[i] == 'L' {
        dist[i].0 = 'l';
      } else {
        dist[i].0 = 'r';
      }
    }


    // 左から見たときのRLのRの距離
    let mut d = std::usize::MAX;
    for i in 0..n {
      if posit[i] == 1 {
        d = i;
      }
      if dist[i].0 == 'l' {
        dist[i].1 = i - d;
      }
    }

    //println!("{:?}", dist);

    // 右から見たときのRLのRの距離
    d = std::usize::MAX;
    for i in (0..n).rev() {
      if posit[i] == 1 {
        d = i;
      }

      if dist[i].0 == 'r' {
        dist[i].1 = d - i;
      }
    }

    for i in 0..n {
      let mut posit = 0;
      let (c, d) = dist[i];

      if c == 'r' {
        posit = (i + d) +  d % 2;
        ans[posit] += 1;
      } else {
        posit = (i - d) + d % 2;
        ans[posit] += 1;
      }
    }

    for e in ans {
      print!("{} ", e);
    }
}


Measured memory_bytes: 8572
#include <string>
#include <vector>
#include <iostream>
using namespace std;
int main(){
  int H,W;
  cin>>H>>W;
  vector<string> map;
  for(int y=0;y<H;y++){
    string s;
    cin>>s;
    int x;
    for(x=0;x<W;x++) if(s[x]!='.') break;
    if(x!=W) map.push_back(s);
  }
  vector<int> removes(W,0);
  for(int x=0;x<W;x++){
    int y;
    for(y=0;y<map.size();y++){
      if(map[y][x]!='.') break;
    }
    if(y==map.size())removes[x]=1;
  }
  for(int y=0;y<map.size();y++){
  	for(int x=0;x<W;x++){
      if(removes[x]==1) continue;
      cout<<map[y][x];
    }
    cout<<"\n";
  }
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
  int n,i,a1;
  cin>>n;
  vector<int> a(n);
  vector<int> b(n);
  for(i=0;i<n;i++) cin>>a[i];
  b=a;
  sort(b.begin(),b.end());
  a1=b[b.size()-1];
  for(i=0;i<n;i++){
    if(a[i]==a1) cout<<b[b.size()-2]<<endl;
    else cout<<a1<<endl;
  }
  return 0;
}

Measured memory_bytes: 3200
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <numeric>
#include <sstream>
#include <iostream>
#include <iomanip>
#define _USE_MATH_DEFINES
#include <cmath>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cfloat>
#include <cmath>
#include <ctime>
#include <cassert>
#include <cctype>
#include <cstdio>
#include <cassert>
using namespace std;

#define EPS 1e-12
#define ull unsigned long long
#define ll long long
#define VI vector<ll>
#define PII pair<ll, ll> 
#define VVI vector<vector<ll> >
#define VVVI vector<vector<vector<ll>>>
#define VVVVI vector<vector<vector<vector<ll>>>>
#define REP(i,n) for(int i=0,_n=(n);(i)<(int)_n;++i)
#define REPR(i,n) for(int i=(int)(n)-1;0<=(i);--i)
#define RANGE(i,a,b) for(int i=(int)a,_b=(int)(b);(i)<_b;++i)
#define RANGER(i,a,b) for(int i=(int)(b)-1,_a=(int)(a);(_a)<=i;--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define ALLR(c) (c).rbegin(), (c).rend()
#define PB push_back
#define MP(a, b) make_pair(a, b)
#define POPCOUNT __builtin_popcount
#define POPCOUNTLL __builtin_popcountll
#define CLEAR(table, v) memset(table, v, sizeof(table));
#define UNIFORM_DOUBLE(a, b) (((b-a)*(double)rand()/RAND_MAX)+a) // [a, b) 
#define UNIFORM_LL(a, b) (ll)UNIFORM_DOUBLE(a, b) // [a, b) 
#define IN(v, lo, hi) ((lo)<=(v) && (v)<(hi))
#define DD(v) cout<<#v<<": "<<v<<endl
template <typename T0, typename T1> std::ostream& operator<<(std::ostream& os, const map<T0, T1>& v) { for( typename map<T0, T1>::const_iterator p = v.begin(); p!=v.end(); p++ ){os << p->first << ": " << p->second << " ";} return os; }
template <typename T0, typename T1> std::ostream& operator<<(std::ostream& os, const pair<T0, T1>& v) { os << v.first << ": " << v.second << " "; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& v) { for( int i = 0; i < (int)v.size(); i++ ) { os << v[i] << " "; } return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const set<T>& v) { vector<T> tmp(v.begin(), v.end()); os << tmp; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const deque<T>& v) { vector<T> tmp(v.begin(), v.end()); os << tmp; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const vector<vector<T> >& v) { for( int i = 0; i < (int)v.size(); i++ ) { os << v[i] << endl; } return os; }
template<typename T>void maxUpdate(T& a, T b) {a = max(a, b);}
template<typename T>void minUpdate(T& a, T b) {a = min(a, b);}

#define MOD 1000000007LL
#define INF (1LL<<60)

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll A,B,C;
	while(cin>>A>>B>>C) {
		cout<<(A==B && B==C ? "Yes" : "No")<<endl;
	}
	
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
namespace mp = boost::multiprecision;
#define ll long long
#define cpp mp::cpp_int
#define dequeue deque
#define rep(i, n) for(int i = 0; i < n; i++)
#define rrep(i, n) for(int i = 1; i <= n; i++)
#define drep(i, n) for(int i = n-1; i >= 0; i--)
#define srep(i, s, t) for (int i = s; i < t; i++)
#define vi vector<int>
#define P pair<ll, ll>
int mod = 1'000'000'000 + 7;
struct edge {
	int to;
	ll cost;
};

void COME_LET_THE_GAMES_BEGIN() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << setprecision(20);
}
void reverse(string* s) {
	reverse((*s).begin(), (*s).end());
}
ll gcd(ll a, ll b) {
	if (b == 0)return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}
ll f(ll n) {
	if (n & 1)return 3 * n + 1;
	return n / 2;
}
int main() {
	COME_LET_THE_GAMES_BEGIN();
	int s;
	cin >> s;
	set<int> x;
	x.insert(s);
	for (int i = 2;; i++) {
		s = f(s);
		if (x.find(s) != x.end()) {
			cout << i << endl;
			return 0;
		}
		x.insert(s);
	}
}

Measured memory_bytes: 256
N = int(input())
aList = list(map(int, input().split()))
BacketSize = [0 for n in range(100010)]
for n in range(N):
    index = aList[n]
    BacketSize[index] += 1
    
for n in range(100010):
    BacketSize[n] += BacketSize[n-1]

i = 0
count = 0
while(BacketSize[i] <= (N / 2)):
    if(BacketSize[i] == (N/2)):
        count += 1
    i += 1
print (count)

Measured memory_bytes: 14396
#include <bits/stdc++.h>
using namespace std;
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; }

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ for(auto it : P) { s << "<" << it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ for(auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s << endl; }


const long long INF = 1LL<<60;
const int MAX = 16;
int N;
vector<long long> A;

vector<vector<long long>> calc(const vector<long long> &a, int offset = 0) {
    vector<vector<long long>> dp(N+1, vector<long long>(MAX, INF));
    for (int j = 0; j < MAX; ++j) dp[0][j] = 0, dp[1][j] = j*2 + offset;
    for (int i = 1; i < N; ++i) {
        long long s = a[N-i-1];
        for (int j = 0; j < MAX; ++j) {
            long long t = a[N-i];
            int need = 0;
            while (s > t) ++need, t *= 4;
            long long add = 0;

            //COUT(s); COUT(t);
            
            if (need >= MAX) {
                add = (need - MAX + 1) * i * 2;

                //cout << need << " -> " << MAX-1 << "(" << i << "): " << add << endl;
                    
                need = MAX-1;

                
            }
            chmin(dp[i+1][j], dp[i][need] + j * 2 + add + offset);
            s *= 4;
        }
    }
    return dp;
}

long long solve() {
    const auto &right = calc(A);
    reverse(A.begin(), A.end());
    const auto &left = calc(A, 1);

    //COUT(left); COUT(right);

    long long res = INF;
    for (int i = 0; i <= N; ++i) chmin(res, left[i][0] + right[N-i][0]);
    return res;
}

int main() {
    cin >> N;
    A.resize(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    cout << solve() << endl;
}


Measured memory_bytes: 67456
while True:
    w,h = map(int,input().split())
    if w == 0:
        break
    c = [input() for i in range(h)]
    dp = [[0]*w for i in range(h)]
    ans = 0
    for i in range(h):
        for j in range(w):
            d = ord(c[i][j]) - ord('0')
            if not (d>=0 and d<=9):
                continue
            dp[i][j] = d
            if i > 0:
                dp[i][j] = max(dp[i][j], dp[i-1][j]*10+d)
            if j > 0:
                dp[i][j] = max(dp[i][j], dp[i][j-1]*10+d)
            ans = max(ans, dp[i][j])
    print(ans)



Measured memory_bytes: 5620
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

using static Input;
using static Util;
class Program
{
    static string s, t;
    static void INPUT()
    {
        s = NextString();
        t = NextString();
    }

    static void OUT()
    {
        var len = s.Length;
        var c = 0;
        for (int i = 0; i < len; i++)
        {
            c += s[i] != t[i] ? 1 : 0;
        }
        Console.WriteLine(c);
    }

    static void Main(string[] args)
    {
#if DEBUG  
        //TESTINPUT();
        INPUT();

#else
        INPUT();
#endif
        OUT();
    }

    static void TESTINPUT()
    {
    }

}

public class Input
{
    public const long MOD = 1000000007;
    public const int INF = 1000000007;
    private static Queue<string> q = new Queue<string>();
    private static void Confirm() { if (q.Count == 0) foreach (var s in Console.ReadLine().Split(' ')) q.Enqueue(s); }
    public static int NextInt() { Confirm(); return int.Parse(q.Dequeue()); }
    public static long NextLong() { Confirm(); return long.Parse(q.Dequeue()); }
    public static string NextString() { Confirm(); return q.Dequeue(); }
    public static double NextDouble() { Confirm(); return double.Parse(q.Dequeue()); }
    public static int[] LineInt() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
    public static long[] LineLong() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
    public static string[] LineString() { return Console.ReadLine().Split(' ').ToArray(); }
    public static double[] LineDouble() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
}

class Util
{
}


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

#define rep(i,n) for (int i=0; i< (n); i++)
typedef std::pair<int, int> P;
typedef long long int ll;

using namespace std;

int main(){
    int n;
    std::cin >> n;
    std::vector<P> p(n);
    rep(i, n) std::cin >> p[i].second >> p[i].first;
    std::sort(p.begin(), p.end());
    ll wt = 0;
    rep(i, n) {
        wt += p[i].second;
        if (p[i].first < wt) {
            printf("No");
            return 0;
        }
    }
    printf("Yes");
    return 0;
}

Measured memory_bytes: 1792
n = int(input())
S = ["m", "c", "x", "i"]
X = [1000, 100, 10, 1]
N = [str(i) for i in range(2, 10)]


for i in range(n) :
    A, B = map(str, input().split())
    A = list(A)
    B = list(B)
    ans = 0
    
    for j in range(len(A)) :
        if(A[j] in S) :
            if(j != 0 and A[j - 1] in N) :
                ans += int(A[j - 1]) * X[S.index(A[j])]
            else :
                ans += X[S.index(A[j])]
        
        else :
            pass
            
    for j in range(len(B)) :
        if(B[j] in S) :
            if(j != 0 and B[j - 1] in N) :
                ans += int(B[j - 1]) * X[S.index(B[j])]
            else :
                ans += X[S.index(B[j])]
        
        else :
            pass
    
    ANS = list(str(ans))
    l = len(ANS)
    
    for j in range(l) :
        if(ANS[j] == "0") :
            pass
        elif(ANS[j] == "1") :
            print(S[j + (4 - l)], end = "")
        else :
            print(ANS[j], S[j + (4 - l)], sep = "", end = "")
        
    print()
    
    
    


Measured memory_bytes: 5624
#include <algorithm>
#include <iostream>
#include <queue>
#include <cmath>
#include <string>
#include <iterator>
#include <map>
#include <set>
#include <iomanip>
#include <vector>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using Graph = vector<vector<int>>;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
#define INF 100000000
#define MAX 200001
#define MOD 1000000007
ll fac[MAX], finv[MAX], inv[MAX];
const int MX = 1000005;

int main(){
    int a,b;cin>>a>>b;
    int ans=0;
    for(int i=1;i<10000;i++){
        if(i*8/100==a && i*10/100==b){
            ans=i;
            break;
        }
        if(i==9999) ans=-1;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
import fractions 
mod = 1000000007;
n = int(input())
a = list(map(int, input().split()))

LCM = 1
for i in a:
    LCM = LCM // fractions.gcd(LCM,i) * i

ans = 0
for i in a:
    ans += (LCM // i)

ans %= mod
print(ans)


Measured memory_bytes: 6200
#define _USE_MATH_DEFINES
#define INF 10000000
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>

using namespace std;

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

static const double EPS = 1e-8;

int main(){
  int N;
  while(~scanf("%d",&N)){
    for(int day=0;day<N;day++){
      int x,y,b,p;
      scanf("%d %d %d %d",&x,&y,&b,&p);

      int min_money = INF;
      for(int i=0;i<=6;i++){
	for(int j=0;j<=6;j++){
	  if(i < b || j < p) continue;
	  
	  int money = INF;
	  if(i >= 5 && j >= 2){
	    money = (int)((double)i * (double)x * 0.8 + (double)j * (double)y * 0.8 + EPS);
	  }
	  else{
	    money = i * x + j * y;
	  }
	  min_money = min(money,min_money);
	}
      }
      printf("%d\n",min_money);
    }
  }
}

Measured memory_bytes: 1188
s = int(input())
l = []
cnt = 1
l.append(s)
while True:
    if s % 2 == 0:
        s /= 2
        if s in l:
            l.append(s)
            print(len(l))
            exit()
        else:
            l.append(s)
    else:
        s = 3*s+1
        if s in l:
            l.append(s)
            print(len(l))
            exit()
        else:
            l.append(s)
            

Measured memory_bytes: 61864
fun main (args: Array<String>) {
  val N = readLine()!!.toInt()
  val A = readLine()!!.split(" ").map {it.toInt()}
  var result = 0L
  for (a in A) {
    result += hoge(a).toLong()
  }
  println(result)
}

fun hoge (a: Int): Int {
  var base = 2
  for (i in 0..100) {
    if (a % base != 0) return i
    base *= 2
  }
  throw Error()
}

Measured memory_bytes: 41464
# 2019/07/17

n,y=map(int,input().split())

def solve():

    for i in range((y//10000)+1):
        for j in range((y//5000)+1):
            k=(y-i*10000-j*5000)//1000
            if k<0:break
            if i+j+k==n:
                return [i,j,k]
                
    else:
        return [-1]*3


print(*solve())

        

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

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

#define ll long long
#define vl vector<ll>
#define vll vector<vl>

const int INF = 1e9;

int main() {
	string s;
	cin >> s;
	if(s=="ABC") cout << "ARC" << endl;
	else cout << "ABC" << endl;
	return 0;
}

Measured memory_bytes: 3620
import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;

struct Edge {
    int to;
    int money;
    long dist;
}

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto S = s[2];
    auto G = new Edge[][](N);
    foreach (i; 0..M) {
        s = readln.split.map!(to!int);
        auto u = s[0] - 1;
        auto v = s[1] - 1;
        auto a = s[2];
        auto b = s[3].to!long;
        G[u] ~= Edge(v, a, b);
        G[v] ~= Edge(u, a, b);
    }
    auto CD = iota(N).map!(_ => readln.split.map!(to!int).array).array;

    auto dp = new long[][](N, N*50+1);
    foreach (ref d; dp) d[] = 1L << 59;
    dp[0][min(S,N*50)] = 0;

    auto pq = new BinaryHeap!(Array!(Edge), "a.dist > b.dist");
    pq.insert(Edge(0, min(S, N*50), 0L));

    while (!pq.empty) {
        auto u = pq.front.to;
        auto dist = pq.front.dist;
        auto money = pq.front.money;
        pq.removeFront;
        foreach (const e; G[u]) {
            auto v = e.to;
            auto next_dist = dist + e.dist;
            auto next_money = money - e.money;
            if (next_money < 0) continue;
            if (dp[v][next_money] <= next_dist) continue;
            dp[v][next_money] = next_dist;
            pq.insert(Edge(v, next_money, next_dist));
        }
        if (money < N*50) {
            auto next_money = min(N*50, money + CD[u][0]);
            auto next_dist = dist + CD[u][1];
            if (dp[u][next_money] <= next_dist) continue;
            dp[u][next_money] = next_dist;
            pq.insert(Edge(u, next_money, next_dist));
        }
    }

    foreach (d; dp[1..N]) d.reduce!min.writeln;
}


Measured memory_bytes: 5380
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#include <cstring>
#include <cassert>


using namespace std;
#define SZ(x) (int)(x.size())
#define REP(i, n) for(int i=0;i<n;++i)
#define FOR(i, a, b) for(int i=a;i<b;++i)
#define RREP(i, n) for(int i=n-1;i>=0;--i)
#define RFOR(i, a, b) for(int i=b-1;i>=a;--i)

#define all(x) begin(x),end(x)
#define dump(x) cerr<<#x<<" = "<<(x)<<endl
#define debug(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<< endl;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<int, int>;
const double eps = 1e-8;
const ll MOD = 1000000007;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;

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

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


template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> p) {
    os << p.first << ":" << p.second;
    return os;
}

template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    os << "[";
    REP(i, SZ(v)) {
        if (i) os << ", ";
        os << v[i];
    }
    return os << "]";
}

// edit

void solve() {
    int a, b, c;
    cin >> a >> b >> c;
    int k;
    cin >> k;
    
    int dec = min(a, k);
    k -= dec;
    int ans = dec;
    
    dec = min(b, k);
    k -= dec;
    
    dec = min(c, k);
    k-= dec;
    ans -= dec;
    
    cout << ans << endl;
}


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
//    std::ifstream in("input.txt");
//    std::cin.rdbuf(in.rdbuf());

    solve();


    return 0;
}


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

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;
	ll k;
	cin>>n>>k;
	vector<pair<ll,ll>> p(n);
	for(int i=0;i<n;++i)
		cin>>p[i].first>>p[i].second;
	sort(p.begin(),p.end());
	ll sum=0;
	for(int i=0;i<n;++i){
		sum+=p[i].second;
		if(sum>=k){
			cout<<p[i].first<<'\n';
			return 0;
		}
	}
}




Measured memory_bytes: 4672
MOD=1000000007
N=int(input())
ls=[int(s) for s in input().split()]
RGB=[0,0,0]
ans=1
for i in range(N):
  if ls[i] in RGB:
    x=RGB.count(ls[i])
    ans=(ans*x)%MOD
    y=RGB.index(ls[i])
    RGB[y]+=1
  else:
    ans=0
    break
print(ans)

Measured memory_bytes: 52908
#include "bits/stdc++.h"
using namespace std;
int main()
{
int n,a,b;
scanf("%d%d%d",&n,&a,&b);
int r=0;
for(int i=1;i<=n;i++)
{
int c=0,t=i;
for(int j=0;j<5;j++)c+=t%10,t/=10;
if(a<=c&&c<=b)r+=i;
}
printf("%d\n",r);
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import _collections
import string
from functools import lru_cache
import heapq

class cin():
    def int():
        return int(sys.stdin.readline().rstrip())
    def string():
        return sys.stdin.readline().rstrip()
    def mapInt():
        return [int(x) for x in cin.string().split()]
    def stringList(n):
        return [input() for i in range(n)]
    def intListList(n):
        return [cin.mapInt() for i in range(n)]
    def intColsList(n):
        return [int(input()) for i in range(n)]
        
class Math():
    def gcd(a,b):
        if b == 0:
            return a
        return Math.gcd(b,a % b)
    def lcm(a,b):
        return (a * b) // Math.gcd(a,b)
    def roundUp(a,b):
        return -(-a // b)
    def toUpperMultiple(a,x):
        return Math.roundUp(a,x) * x
    def toLowerMultiple(a,x):
        return (a // x) * x
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3,d + 1,2):
            if n % i == 0:
                return False
        return True


MOD = int(1e09) + 7

def main():
    S = cin.string()
    N = len(S)
    ans = 0
    for i in range(N - 1):
        if S[i] != S[i + 1]:
            ans +=1
    print(ans)
    return

if __name__ == "__main__":
    main()


Measured memory_bytes: 40304
#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(){
    int N; cin >> N;
    vector<int> a(N);
    rep(i, N) cin >> a[i];
    map<int, ll> m;
    ll ans = 0;
    rep(i, N){
        m[a[i]]++;
        ans += a[i];
    }
    int Q; cin >> Q;
    vector<ll> sum;
    rep(i, Q){
        ll B, C; cin >> B >> C;
        ans -= m[B] * B;
        ans += m[B] * C;
        m[C] += m[B];
        m[B] = 0;
        sum.push_back(ans);
    }

    rep(i, Q) cout << sum[i] << endl;
}

Measured memory_bytes: 10464
#!/usr/bin/env python3
# -*- coding: utf-8 -*-



def main():
    N = int(input())
    S = input()
    T = input()

    len_common = N
    for i in range(N):
        sub = S[i:]
        if T.startswith(sub):
            break
        len_common -= 1

    print(len(S) + len(T) - len_common)

if __name__ == "__main__": main()


Measured memory_bytes: 3068
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<map>
#include<stack>
#include<queue>
#include<bitset>

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

using namespace std;

typedef long long int lli;
typedef long long ll;
typedef vector<int> vi;

int main() {
	int a, b;

	cin >> a >> b;

	if (b%a == 0) {
		cout << a + b;
	}
	else {
		cout << b - a;
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf = 1e18;
int n;
ll cst[26], sat[366][26], last[26], tmp[26];
int main(){
	scanf("%d", &n);
	memset(last, 0ll, sizeof(last));
	for(int i=0; i<26; i++) scanf("%lld", &cst[i]);
	for(int i=0; i<n; i++) for(int j=0; j<26; j++)
		scanf("%lld", &sat[i][j]);
	ll res = 0ll;
	for(int nw, i=0; i<n; i++){
		memset(tmp, 0ll, sizeof(tmp));
		for(nw=0; nw<26; nw++){
			tmp[nw] += sat[i][nw];
			for(int j=0; j<26; j++) if(j != nw)
				tmp[nw] -= cst[j] * (i+1-last[j]);
		}
		ll get = -inf; int id = -1;
		for(nw=0; nw<26; nw++) 
			if(get < tmp[nw]){
				get = tmp[nw]; id = nw;
			}else if(get == tmp[nw] && cst[nw] > cst[id]){
				get = tmp[nw]; id = nw;
			}
		printf("%d\n", id+1);
		last[id] = i+1; res += tmp[nw];
	}
	return 0;
}

Measured memory_bytes: 3888
from collections import deque
n = int(input())
a = list(map(str,input().split()))
b = deque()
for i in range(n):
    if i%2 == 0:
        b.append(a[i])
    else:
        b.appendleft(a[i])
if n%2 == 0:
    print(" ".join(b))
else:
    b.reverse()
    print(" ".join(b))

Measured memory_bytes: 26564
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;
int main(void) {
  int x, y;
  cin >> x >> y;
  cout << abs(x-y) << endl;
  return 0;
}



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

using namespace std;

struct Edge
{
    int to;
    int cost;
};

int main()
{
    int N;
    cin >> N;
    vector<Edge> edges[N];
    for (int i = 0; i < N - 1; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        u--;
        v--;
        edges[u].push_back(Edge{v, w});
        edges[v].push_back(Edge{u, w});
    }
    vector<bool> ans(N, false);
    queue<pair<int, Edge>> bfs;
    for (auto e : edges[0])
    {
        bfs.emplace(0, e);
    }
    //cout << endl;
    ans[0] = false;
    while (!bfs.empty())
    {
        auto b = bfs.front();
        bfs.pop();
        int from = b.first;
        Edge edge = b.second;
        //cout << from << " " << edge.to << " " << edge.cost << endl;
        ans[edge.to] = edge.cost % 2 == 0 ? ans[from] : !ans[from];
        for (auto e : edges[edge.to])
        {
            if (e.to != from)
                bfs.emplace(edge.to, e);
        }
    }
    for (auto a : ans)
    {
        cout << (int)a << endl;
    }
}


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

int main() {
	int N,ans = 0,tmp = -10;
	cin >> N;
	vector<vector<int>> data(3,vector<int>(N));
	rep(i,2){
        rep(j,N){
            cin >> data.at(i).at(j);
            //cout << data.at(i).at(j);
        }
        //cout << endl;
    }
  	rep(j,N-1){
      cin >> data.at(2).at(j);
      //out << data.at(2).at(j);
    }
    //cout << endl;
  	rep(i,N){
        //cout << data.at(1).at(data.at(0).at(i)-1) << endl;
        ans += data.at(1).at(data.at(0).at(i)-1);
        if(tmp + 1 == data.at(0).at(i)-1){
            ans += data.at(2).at(tmp);
          }
        tmp = data.at(0).at(i)-1;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
h, w = map(int, input().split())

grid = ["*" + input() + "*" for _ in range(h)]
grid.append("*" * (w + 2))
grid.insert(0, "*" * (w+2))

for y in range(1, h+1):
    for x in range(1, w+1):
        if grid[y][x] == "#":
            if grid[y+1][x] == "#" or \
               grid[y-1][x] == "#" or \
               grid[y][x+1] == "#" or \
               grid[y][x-1] == "#":
               continue
            else:
                print("No")
                exit()

print("Yes")


Measured memory_bytes: 9100
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, acos, asin, atan, sqrt, tan, cos, pi
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n, m = LI()
hor = []
ver = []
x_co = {-INF, INF}
y_co = {-INF, INF}
for _ in range(n):
    a, b, c = LI()
    x_co.add(a)
    x_co.add(b)
    y_co.add(c)
    ver += [(a, b, c)]

for _ in range(m):
    d, e, f = LI()
    x_co.add(d)
    y_co.add(e)
    y_co.add(f)
    hor += [(d, e, f)]


x_co = sorted(x_co)
y_co = sorted(y_co)
XD = {val:i for i,val in enumerate(x_co)}
YD = {val:i for i,val in enumerate(y_co)}
x_len = len(x_co) * 2 - 1
y_len = len(y_co) * 2 - 1
grid = [[0] * y_len for _ in range(x_len)]
x_range = [0] * x_len
y_range = [0] * y_len
x_range[0] = x_range[-1] = y_range[0] = y_range[-1] = INF
for i in range(len(x_co) - 1):
    x_range[i * 2 + 1] = x_co[i + 1] - x_co[i]
    if x_co[i] <= 0 <= x_co[i + 1]:
        sx = i * 2 + 1

for j in range(len(y_co) - 1):
    y_range[j * 2 + 1] = y_co[j + 1] - y_co[j]
    if y_co[j] <= 0 <= y_co[j + 1]:
        sy = j * 2 + 1

for a, b, c in ver:
    yi = YD[c] * 2
    for xi in range(XD[a] * 2,  XD[b] * 2 + 1):
        grid[xi][yi] = 1


for d, e, f in hor:
    xi = XD[d] * 2
    for yi in range(YD[e] * 2,  YD[f] * 2 + 1):
        grid[xi][yi] = 1


ans = x_range[sx] * y_range[sy]
grid[sx][sy] = 1


ans = 0
dq = deque([(sx, sy)])
grid[sx][sy] = 1
diff = ((0, 1), (1, 0), (-1, 0), (0, -1))
ans += x_range[sx] * y_range[sy]
while dq:
    x, y = dq.popleft()
    for dx, dy in diff:
        nx, ny = dx + x, dy + y
        if grid[nx][ny]:
            continue
        nx += dx;
        ny += dy
        if grid[nx][ny]:
            continue
        grid[nx][ny] = 1
        dq.append((nx, ny))
        ans += x_range[nx] * y_range[ny]
        if ans >= INF:
            print("INF")
            exit()

print(ans)






Measured memory_bytes: 441668
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld =long double;
const ld eps = 1e-9;

int solve(const vector<string>&sts, const vector<string>&revsts, string st,const int k) {
	int ans=0;
	if (k == 0) {
		auto lt = lower_bound(sts.begin(), sts.end(), st);
		auto rt = upper_bound(sts.begin(), sts.end(), st);
		ans = rt - lt;
	}
	else if (k == 1) {
		auto lt = lower_bound(sts.begin(), sts.end(), st);
		st.back()++;
		auto rt = lower_bound(sts.begin(), sts.end(), st);
		ans = rt - lt;
	}
	else {
		string revst(st);
		reverse(revst.begin(), revst.end());
		auto lt = lower_bound(revsts.begin(), revsts.end(), revst);
		revst.back()++;
		auto rt = lower_bound(revsts.begin(), revsts.end(), revst);
		ans = rt - lt;
	}
	return ans;
}


int main()
{
	int N,Q;cin>>N>>Q;
	vector<string>sts,revsts;
	for (int i = 0; i < N; ++i) {
		string st;cin>>st;
		sts.push_back(st);
		reverse(st.begin(),st.end());
		revsts.push_back(st);
	}
	sort(sts.begin(),sts.end());
	sort(revsts.begin(),revsts.end());
	while (Q--) {
		string st;cin>>st;


		int k=0;
		if (st[0] == '*') {
			st=st.substr(1);
			k=2;
		}
		else if (st.back() == '*') {
			st=st.substr(0,st.size()-1);
			k=1;
		}

		int x=st.find('?');

		int ans=0;
		if (x == string::npos) {
			ans=solve(sts,revsts,st,k);
		}
		else {
			for (int c = 'a'; c <= 'z'; ++c) {
				st[x]=c;
				ans+=solve(sts,revsts,st,k);
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}


Measured memory_bytes: 11880
from collections import deque

N = int(input())
S = [[]for i in range(N)]
for i in range(N-1):
    u,v,w = map(int,input().split())
    S[u-1].append([v-1,w])
    S[v-1].append([u-1,w])
Node = [None]*N
Node[0] = True
queue = deque([0])
while queue != deque([]):
    p = queue.popleft()
    for u,w in S[p]:
        if Node[u] == None:
            queue.append(u)
            Node[u] = (Node[p])^(w%2==1)
for i in range(N):
    print([0,1][Node[i]])

Measured memory_bytes: 45368
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int INF = 1LL << 30;
int MOD = 1e9+7;
int H,W,A,B;
ll powmod(ll x,ll n){
    if(n == 0)return 1;
    ll ans = powmod(x*x%MOD,n/2);
    if(n % 2)ans = ans * x % MOD;
    return ans;
}
ll divmod(ll a,ll b){
    return ((a%MOD) * (powmod(b,MOD-2)%MOD)) % MOD;
}
ll combi(ll n,ll r){
    ll num = 1;
    for(ll i = 1;i <= n;i++){
        num = divmod((n-i+1)*num,i);
    }
    return num;
}
void make_table(ll n,ll r,ll *table){
    //rCr ~ nCr
    table[0] = 1;
    for(int i = 1;i < W;i++){
        table[i] = divmod(table[i-1]*(r+i),i); 
    }
}
main(){
    cin >> H >> W >> A >> B;
    ll t1[W] = {},t2[W] = {};
    make_table(H+W-A-B,H-A-1,t1);
    make_table(W,A-1,t2);
    /*
    for(int i = 0;i < W;i++){
        cout << t1[i] << endl;
    }cout << endl;
    for(int i = 0;i < W;i++){
        cout << t2[i] << endl;
    }
    */
    ll ans = 0;
    for(int i = 0;i < W-B;i++){
//        cout << t1[W-i-1] << " " << t2[i] << endl;
        (ans += t1[W-i-1] * t2[i]) %= MOD;
    }
    cout << ans << endl;
}


Measured memory_bytes: 1792
s = gets.chomp.reverse
T = ["maerd", "remaerd", "esare", "resare"]

until s.empty? do
  flg = true
  T.each{|t|
    if ! (/\A#{t}/ =~ s).nil? then
      s = s[t.size..-1]
      flg = false
    end
  }
  break if flg
end

puts s.empty? ? 'YES' : 'NO'


Measured memory_bytes: 7036
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


h, w = LI()
s = [input() for _ in range(h)]
dp = [[0] * w for _ in range(h)]
dp[0][0] = 1
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            continue
        if i and s[i-1][j] == ".":
            dp[i][j] += dp[i-1][j]
        if j and s[i][j-1] == ".":
            dp[i][j] += dp[i][j-1]
        dp[i][j] %=mod

print(dp[h-1][w-1])

Measured memory_bytes: 90248
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
const ll MOD = 1e9+7;
const ll MOD2 = 998244353;
const int inf = INT_MAX;
const ll INF = LLONG_MAX;
const string alpha = "abcdefghijklmnopqrstuvwxyz";

int main(){
    int N, M;
    cin >> N >> M;
    ll X[M];
    rep(i, M) cin >> X[i];
    ll sum = 0;
    sort(X, X+M);
    ll d[M-1];
    rep(i, M-1) d[i] = X[i+1]-X[i];
    sort(d, d+M-1);
    rep(i, M-N){
        sum += d[i];
    }
    cout << sum;
}

Measured memory_bytes: 1792
while true
    a, op, b = gets.split(" ")
    case op
    when '?'
        break
    when '+'
        puts a.to_i+b.to_i
    when  '-'
        puts a.to_i-b.to_i
    when '*'
        puts a.to_i*b.to_i
    when '/'
        puts a.to_i/b.to_i
    end
end

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

#define y1 as214
#define ii pair < int , int >
#define iii pair < int , ii >
#define iv pair < ii , ii >

#define fi first
#define se second
#define fr front()
#define pb push_back
#define t top()

#define FOR(i , x , n) for(int i = x ; i <= n ; ++i)
#define REP(i , n) for(int i = 0 ; i < n ; ++i)
#define FORD(i , x , n) for(int i = x ; i >= n ; --i)

#define ll long long
#define oo 1e17
#define int long long

const int N = 3e3 + 5;
int n;
int dp[N][N];
char f1[N] , f2[N];

void tr(int x , int y)
{
    if(x != 0 && y != 0)
    {
        if(dp[x][y] == dp[x - 1][y])
            tr(x - 1 , y);
        else if(dp[x][y] == dp[x][y - 1])
            tr(x , y - 1);
        else
        {
            tr(x - 1 , y - 1);
            cout << f1[x];
        }
    }
}

main()
{
    //freopen("F.inp","r",stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> f1;
    cin >> f2;
    int x = strlen(f1);
    int y = strlen(f2);
    FORD(i , x , 1)
        f1[i] = f1[i - 1];
    FORD(i , y , 1)
        f2[i]= f2[i - 1];
    FOR(i , 1 , x)
        FOR(j , 1 , y)
            {
                if(f1[i] == f2[j])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = max(dp[i - 1][j] , dp[i][j - 1]);
            }
    tr(x , y);
}


Measured memory_bytes: 70784
import java.util.*;

class Main {
    final Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        new Main().run();
    }

    private void run() {
         int n = sc.nextInt();
         int even = n/2;
         double odd = n-even;
         System.out.println(odd/n);
    }
}


Measured memory_bytes: 21972
#include<bits/stdc++.h>
#define ll long long
using namespace std;
template <typename T> void read(T &x){
	x=0;char ch=getchar();int fh=1;
	while (ch<'0'||ch>'9'){if (ch=='-')fh=-1;ch=getchar();}
	while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	x*=fh;
}
string s;
int A,B,C,D,n;
bool pa(int l,int r){
	for (int i=l;i<r;i++)if (s[i-1]=='#'&&s[i]=='#') return 0;
	return 1;
}
int main(){
	cin>>n>>A>>B>>C>>D;
	cin>>s;
	if (C>D){
		bool an=0;
		for (int i=A;i<=C-2;i++){
			if (s[i-1]!='#'&&s[i]!='#'&&s[i+1]!='#'&&i+1>=B&&i+1<=D)an=1;
		}
		if (an&&pa(B,D)&&pa(A,C))puts("Yes");else puts("No");
	}else{
		if (pa(B,D)&&pa(A,C))puts("Yes");else puts("No");
	}
	return 0;
}

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

int main(){
  int H,W;
  cin >> H >> W;
  string S[H];
  rep(i,H){
    cin >> S[i];
  }
  int T[H][W];
  int Y[H][W];
  rep(i,H)rep(j,W){
    T[i][j]=-1;
    Y[i][j]=-1;
  }
  rep(i,H)rep(j,W){
    if(S[i][j]=='.'){
      if(T[i][j]==-1){
        int d=0;
        while(i+d<H and S[i+d][j]=='.'){
          d++;
        }
        rep(k,d) T[i+k][j]=d;
      }
      if(Y[i][j]==-1){
        int d=0;
        while(j+d<W and S[i][j+d]=='.'){
          d++;
        }
        rep(k,d) Y[i][j+k]=d;
      }
    }
  }
  int ans=0;
  rep(i,H)rep(j,W){
    if(S[i][j]=='.'){
      ans=max(ans,max(0,T[i][j]-1)+max(0,Y[i][j]-1)+1);
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 35584
package main

import (
	"fmt"
)

func main() {
	var s string
	fmt.Scanf("%s", &s)
	lens := len(s)

	out := ""
	for i := 0; i < lens; i++ {
		switch char := s[i : i+1]; char {
		case "0":
			out += "0"
		case "1":
			out += "1"
		case "B":
			if len(out) != 0 {
				out = out[:len(out)-1]
			}
		}
	}

	fmt.Printf("%s\n", out)
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define ll long long
#define maxn 305 /*rem*/
#define db double
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define fi first
#define se second
using namespace std;
ll dp[maxn][maxn]; 
int c[maxn][maxn];
int main() {
	int n, k, m;
	cin >> n >> k >> m;
	for (int i = 0; i < maxn; i++) {
		for (int j = 0; j <= i; j++) {
			if (j == 0) c[i][j] = 1;
			else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % m;
		}
	}
	for (int i = 0; i <= k; i++)
		for (int j = 0; j <= n; j++) {
			if (i == 0) {
				if (j == 0) dp[i][j] = 1;
				else dp[i][j] = 0;
			}
			else {
				dp[i][j] = dp[i - 1][j];
				for (int s = 1; s <= j; s++) {
					ll nans = c[j][s - 1] * dp[i - 1][s - 1] % m * dp[i][j - s] % m;
					dp[i][j] += nans, dp[i][j] %= m;
				}
			}
		//	if (dp[i][j]) cout << i << ' ' << j << ' ' << dp[i][j] << endl;
		}
	cout << dp[k][n] << endl;
	return 0;
}


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

int main(){
int N,Y;
  cin>>N>>Y;
  
  for(int x=0; x<=N; x++){
   for(int y=0; y<=N; y++){
    int z=N-x-y;
     if(0<=z && z<=N && x*10000+y*5000+z*1000==Y){
         cout<<x<<endl;
         cout<<y<<endl;
         cout<<z<<endl; return 0;}
   }
  }
    
  cout<<"-1 -1 -1";
}

Measured memory_bytes: 256
//JOI2010-2011本選問４歩くサンタクロース(Walking Santa)
#include<iostream>
#include<cstdio>
#include<deque>
#include<algorithm>
using namespace std;
int main(){

	long long sum = 0LL, osum = 0LL;
	long long f1, f2, f3, cnt, w, h, L, HL, temp, oxy[2][2], *LXY[2], ox, oy, max = 0;
	deque<long long> XY[2];
	scanf("%lld %lld",&w, &h);
	scanf("%lld",&L);
	for(f1 = 0; f1 < 2; f1++)
		LXY[f1] = new long long [L];
	//100k
	for(f1 = 0; f1 < L; f1++){
		scanf("%lld %lld",&LXY[0][f1], &LXY[1][f1]);
		XY[0].push_back(LXY[0][f1]);
		XY[1].push_back(LXY[1][f1]);
	}
	//1m
	stable_sort( XY[0].begin(), XY[0].end() );
	stable_sort( XY[1].begin(), XY[1].end() );
	HL = (L + 1) / 2;
	//x軸での最小値の点、y軸での最小値の点を探す
	//200k
	if(L == 1){
		printf("0\n");
		printf("%lld %lld\n",LXY[0][0],LXY[1][0]);
	}
	else{
		for(f1 = 0; f1 < 2; f1++){
			cnt = 1;
			temp = XY[f1][cnt-1];
			while(cnt < HL){
				while(cnt < HL && temp == XY[f1][cnt])
					cnt++;
				if(cnt < HL)
					temp = XY[f1][cnt];
			}
			oxy[0][f1] = XY[f1][cnt-1];
			oxy[1][f1] = XY[f1][cnt];
		}
		//400k
		for(f2 = 0; f2 < 2; f2++){
			for(f3 = 0; f3 < 2; f3++){
				sum = 0LL;
				max = 0LL;
				for(f1 = 0; f1 < L; f1++){
					temp = (long long)abs(LXY[0][f1] - oxy[f2][0]) + abs(LXY[1][f1] - oxy[f3][1]);
					sum += temp * 2;
					if(max < temp)
						max = temp;
				}
				sum -= max;
				if(osum == 0 || osum > sum){
					osum = sum;
					ox = oxy[f2][0];
					oy = oxy[f3][1];
				}
			}
		}
		printf("%lld\n", osum);
		printf("%lld %lld\n", ox, oy);
	}
	return 0;
}

Measured memory_bytes: 4708
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <map>
#include <vector>
using namespace std;

string s;
int main(int argc, char const *argv[]) {
  cin >> s;
  string s_odd;
  for (size_t i = 0; i < s.size(); i++) {
    if (i % 2 == 0) {
      s_odd += s[i];
    }
  }
  cout << s_odd << endl;
  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using lint = int64_t;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define all(v)    begin(v), end(v)
#define in        []{lint n; cin>>n; return n;}()

int main(){
    int N = in;
    vector<int> A(N);
    rep( i, N ) A[i] = in;
    int M = INT_MIN;
    rep( i, N ) M = max( M, A[i] );
    int R = INT_MIN;
    rep( i, N ) if( A[i] != M && abs(M/2-A[i]) < abs(M/2-R) ) R = A[i];
    cout << M << " " << R << "\n";
}


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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int k;
    string s;
    cin>>k;
    cin>>s;
    int m = s.size();
    if(m<=k)
    {
      cout<<s;
    }
    else
    {
      string t = s.substr(0,k);
      cout<<t<<"...";
    }
    return 0;
}

Measured memory_bytes: 3612
import java.util.*;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        boolean ret = true;
        if(s.contains("N")&&(!s.contains("S"))){
            ret = false;
        }
        if(!s.contains("N")&&(s.contains("S"))){
            ret = false;
        }
        if(s.contains("E")&&(!s.contains("W"))){
            ret = false;
        }
        if(s.contains("W")&&(!s.contains("E"))){
            ret = false;
        }

        if(ret) System.out.print("Yes");
        else System.out.print("No");
    }
 }

Measured memory_bytes: 9428
N = int(input())

X=[]
for i in range(N):
    S, P = input().split()
    X.append([S,int(P)])

sort1=sorted(X, key=lambda x:x[1], reverse=True)
sort2=sorted(sort1, key=lambda x:x[0])

for j in range(N):
    print(X.index(sort2[j])+1)

Measured memory_bytes: 3060