akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <functional>
using namespace std;

//素数判定
inline bool IsPrime(int p) {
	if (p == 1) return false;
	for (int i = 2; i <= sqrt(p); i++) {
		if (p%i == 0) return false;
	}
	return true;
}

//10進数の自然数の桁数を返す
inline int GetDigit(int num) {
	return (int)log10(num) + 1;
}

//各位の和を返す
int GetDigitsSum(int num) {
	int N = 0;
	while (num > 0) {
		N += num % 10;
		num /= 10;
	}
	return N;
}



//異なるn個からr個の整数を取り出す組合せの数を求める
int combination(int n, int r) {
	if (r == 0 || n == r) {
		return 1;
	}
	else if (r == 1) {
		return n;
	}
	else {
		return combination(n - 1, r - 1) + combination(n - 1, r);
	}

}

int main() {
	string s;
	cin >> s;
	for (int i = 0; i < 3; i++)
	{
		if (s[i] == '1') {
			s[i] = '9';
		}
		else {
			s[i] = '1';
		}
	}

	cout << s << endl;
	return 0;
}


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


using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVC vector<vector<char>>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define fore(i,a) for(auto &i:a)
typedef pair <int, int> P;
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

const int  INF = 1 << 29;
const ll INFL = 1LL << 60;
const ll mod = 998244353;
#define VQ vector<priority_queue<pair<ll,vector<int>>>>
#define VQQ vector<vector<pair<ll,vector<int>>>>


int main() {

	int r;
	cin >> r;
	cout << r * r << endl;

}


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

vector<string> StringSplit(const string &str, char sep)
{
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while(getline(ss, buffer, sep) ) {
        v.push_back(buffer);
    }
    return v;
}

int main(int argc, const char * argv[]) {
    int N;
    
    cin >> N;
    
    vector<pair<string, int>> SP;
    for (int i = 0; i < N; i++) {
        pair<string, int> p;
        ostringstream ss;
        cin >> p.first >> p.second;
        ss << (i + 1);
        p.first = p.first + "_" + ss.str();
        SP.push_back(p);
    }
    sort(SP.begin(), SP.end());
    
    for (int i = 0; i < N - 1; i++) {
        for (int j = i + 1; j < N; j++) {
            vector<string> s1 = StringSplit(SP[i].first, '_');
            vector<string> s2 = StringSplit(SP[j].first, '_');
            if (strcmp(s1[0].c_str(), s2[0].c_str()) == 0) {
                if (SP[i].second < SP[j].second) {
                    swap(SP[i], SP[j]);
                }
            }
        }
    }
    
    for (int i = 0; i < N; i++) {
        vector<string> s1 = StringSplit(SP[i].first, '_');
        cout << s1[1] << endl;
    }
    
    return 0;
}


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

#define FOR(i, a, b) for (int i=a; i<b; i++)
#define For(i, a) for (int i=0; i<a; i++)
#define FORR(i,a,b) for (int i = a; i >= b; i--)
#define Forr(i,a) for (int i = a; i >= 0; i--)

#define deb(...) cerr << "[" << #__VA_ARGS__ << "] : [", DBG(__VA_ARGS__)
void DBG() { cerr << "]\n";}
template<typename T, typename ...Args> void DBG(T first, Args... args)
{cerr << first; if(sizeof...(args))cerr<<", "; DBG(args...); }

const int mod = 1e9+7;

int mul(int x,int y){
  int res = x*y;
  if(res >= mod)res%=mod;
  return res;
}

int add(int x, int y){
  int res = x+y;
  if(res >= mod)res-=mod;
  return res;
}
int sub(int x, int y){
  int res = x-y;
  if(res<0)res+=mod;
  return res;
}

int power(int x, int y){
  int res = 1;
  while(y){
    if(y&1)res = mul(res,x);
    y = y>>1;
    x = mul(x,x);
  }
  return res;
}


void solve(){
  int n; cin >> n;
  if(n<2){
    cout << 0 << "\n";
    return;
  }
  int ans=power(10,n);
  ans = sub(ans,mul(2,power(9,n)));
  ans = add(ans,power(8,n));
  cout << ans << "\n";
}

int32_t main(){
  ios_base:: sync_with_stdio(false);
  cin.tie(0);
  int t=1;
  for(int tt=1;tt<=t;tt++){
    solve();
  }
}

Measured memory_bytes: 3588
#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

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

    constexpr ll MOD = 1e9 + 7;

    //dp[i][j][k] := 上からi段目を見ている状況でj個保留しているものがあり
    //               確定しているものの中では奇妙さがkである場合の数
    vector<vector<vector<ll>>> dp(n + 1, vector<vector<ll>>(n + 2, vector<ll>(k + 1, 0)));
    dp[0][0][0] = 1;

    for (ll i = 1; i <= n; i++) {
        for (ll j = 0; j <= i; j++) {
            for (ll l = 0; l <= k; l++) {
                if (l - 2 * j < 0) {
                    continue;
                }

                //i同士で繋ぐまたは片方のiと保留のものを繋ぐ jが変わらないような遷移
                //遷移で保留中のもの線をまたぐので奇妙さが2j増える
                (dp[i][j][l] += (2 * j + 1) * dp[i - 1][j][l - 2 * j]) %= MOD;

                //両方保留中のものへ繋ぐ j+1からjへ減るような遷移
                (dp[i][j][l] += (j + 1) * (j + 1) * dp[i - 1][j + 1][l - 2 * j]) %= MOD;

                if (j == 0) {
                    continue;
                }
                //両方保留する j-1からjへ増えるような遷移
                (dp[i][j][l] += dp[i - 1][j - 1][l - 2 * j]) %= MOD;
            }
        }
    }

    cout << dp[n][0][k] << endl;
}

Measured memory_bytes: 53120
#include <cstring>
#include <map>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>

using namespace std;

int arr[100010];

int main()
{

//    freopen("D:\\Code\\TestData\\data_in.txt","r",stdin);
//    freopen("D:\\Code\\TestData\\data_in.txt","w",stdout);
//    printf("100000\n");
//    for(int i=1;i<=100000;i++){
//        printf("%d ",i);
//    }
//    printf("\n");
    int loop;

    while(~scanf("%d", &loop))
    {
        for(int i=1;i<=loop;i++){
            scanf("%d",&arr[i]);
        }

        bool f=false;
        int pre=0;
        int res=0;
        for(int i=1;i<=loop;i++){
            if(arr[i]==i){
                if(f){
                   if(i-pre==1){
                        f=false;
                   }else{
                        res++;
                        f=false;
                   }
                }else{
                    pre=i;
                    f=true;
                    res++;
                }
            }else{
                f=false;
            }
        }
        printf("%d\n",res);

    }
    return 0;
}


Measured memory_bytes: 640
use std::io;
use std::io::BufRead;

fn answer(n: u64) {
    println!("! {}", n);
}


fn main() {
    let mut sc = Scanner::new(std::io::stdin());

    if favorite(&mut sc, 10_000_000_000) {
        let mut ans = 1;
        loop {
            if favorite(&mut sc, ans * 2) {
                answer(ans);
                return;
            }
            ans *= 10;
        }
    }

    let mut dig = 1;
    let mut ten = 1;
    loop {
        if !favorite(&mut sc, ten * 10) {
            break;
        }
        ten *= 10;
        dig += 1;
    }

    let mut head = 0;
    for i in 0..dig {
        let mut left: i32 = -1;
        let mut right: i32 = 10;
        while right - left > 1 {
            let mid = (left + right) / 2;
            if favorite(&mut sc,
                        (head * 10 + mid as u64) * (if i + 1 == dig { 10 } else { 1 })) {
                if i + 1 < dig {
                    left = mid;
                } else {
                    right = mid;
                }
            } else {
                if i + 1 < dig {
                    right = mid;
                } else {
                    left = mid;
                }
            }
        }
        head = head * 10 + left as u64;
    }
    answer(head + 1);
}

fn favorite(sc: &mut Scanner<std::io::Stdin>, n: u64) -> bool {
    if n == 0 {
        return true;
    }
    println!("? {}", n);
    sc.next::<String>().unwrap() == "Y".to_string()
}

/// Scanner
///
/// # Example
/// ```
/// use contest::io::scanner;
/// let mut sc = scanner::Scanner::new("1 2 \n\n \r\t \n 3.5".as_bytes());
/// assert_eq!("1".to_string(), sc.next::<String>().unwrap());
/// assert_eq!(2, sc.next().unwrap());
/// assert_eq!(3.5, sc.next().unwrap());
/// assert_eq!(None, sc.next::<i32>());
/// ```

pub struct Scanner<R: io::Read> {
    br: io::BufReader<R>,
    // Read tokens are stored in reversed order per line.
    buf: Vec<String>,
}

impl<R: io::Read> Scanner<R> {
    pub fn new(r: R) -> Scanner<R> {
        Scanner {
            br: io::BufReader::new(r),
            buf: vec![],
        }
    }
    #[inline]
    pub fn next<T>(&mut self) -> Option<T>
        where T: std::str::FromStr,
              T::Err: std::fmt::Debug
    {
        self.next_string().map(|s| s.parse::<T>().expect("Parse failed: "))
    }
    fn next_string(&mut self) -> Option<String> {
        self.buf.pop().or_else(|| match self.update() {
            true => self.next_string(),
            false => None,
        })
    }
    #[inline]
    fn update(&mut self) -> bool {
        let mut s = String::new();
        let res = self.br.read_line(&mut s);
        match res.expect("I/O error.") {
            0 => false,
            _ => {
                self.buf = s.split_whitespace().map(|x| x.to_string()).rev().collect();
                true
            }
        }
    }
}


Measured memory_bytes: 4692
import java.io.*;

class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br =
			new BufferedReader(new InputStreamReader(System.in));

			String[] line = br.readLine().split(" ");
			int a = Integer.parseInt(line[0]);
			int b = Integer.parseInt(line[1]);

			if((a - b) == 0){
				System.out.println("a == b");
			}
			if((a - b) > 0){
				System.out.println("a > b");
			}
			if((a - b) < 0){
				System.out.println("a < b");
			}
	}
}

Measured memory_bytes: 24136
s = input()
t = input()

s = [x for x in s]
t = [x for x in t]

# 合致しているか返す関数
def check_match(s, t):
    result = ['?' for _ in range(len(s))]
    for i in range(len(s)):
        s_ = s[i]
        t_ = t[i]
        if s_ == '?':
            result[i] = t_
        elif t_ == '?':
            result[i] = s_
        elif s_ == t_:
            result[i] = t_
        else:
            return None

        output = ''
        for x in result:
            output += x if x != '?' else 'a'
    return output
  
diff = len(s) - len(t)
results = []

for i in range(diff+1):
    t_new = ['?'] * i + t + ['?'] * (diff - i) 
    result = check_match(s, t_new)
    
    if result:
        results.append(result)
        
if len(results):
    print(sorted(results)[0])
else:
    print('UNRESTORABLE')

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

#define rep(i,n) for(ll i=0;i<n;++i)
#define all_map(itr,mp) for(auto itr=mp.begin();itr!=mp.end();itr++)
#define ALL(a) (a).begin(),(a).end()
#define chmax(x, y) x = max(x,y);
const int INF=1001001001;

using namespace std;
using ll  = long long;
using pll = pair<ll, ll>;

int main(){
  int n,m;
  cin>>n>>m;
  vector <pair<int,int>> key;
  for (int i=0;i<m;i++){
    int a,b;
    cin>>a>>b;
    int s=0;
    rep(j,b){
      int c;
      cin>>c;
      c--;
      s=s|1<<c;
    }
    key.emplace_back(s,a);
  }
  vector<int> dp(1<<n, INF);
  dp[0]=0;
  rep(i,1<<n){
    rep(j,m){
      int s=i|key[j].first;
      int a=key[j].second;
      dp[s]=min(dp[s],dp[i]+a);
    }
  }
  int ans=dp.back();
  if (ans==INF) cout<<-1;
  else{
    cout<<ans;
  }




    }


Measured memory_bytes: 256
import math
import sys
def main():
    n, m = map(int, input().split())
    a = [[0 for i in range(2)] for j in range(m)]
    for i in range(m):
        a[i] = list(map(int, input().split()))

    ans = [0 for i in range(n)]
    count = 0

    for _, contents in enumerate(a):
        if contents[0] == 1 and contents[1] == 0 and n != 1:
            print(-1)
            sys.exit()
        else:
            ans[contents[0]-1] = contents[1]

        #同じ場所に矛盾がないか
        for i , contents_2 in enumerate(a):
                if contents[0] == contents_2[0] and contents[1] != contents_2[1]:
                    count += 1
                    if count == 2:
                        print(-1)
                        sys.exit()

    if ans[0] == 0 and n!= 1:
        ans[0] = 1
    ans = map(str, ans)

    print(int(''.join(ans)))

if __name__ == '__main__' :
    main()


Measured memory_bytes: 3064
#pragma region
#include <bits/stdc++.h>
using namespace std;
inline void ci(void){
  return;
}
template <typename First, typename... Rest>
void ci(First& first, Rest&... rest){
  cin >> first;
  ci(rest...);
  return;
}
inline void co(void){
  cout << "\n";
  return;
}
template <typename First, typename... Rest>
void co(First first, Rest... rest){
  cout << first << " ";
  co(rest...);
  return;
}
#define ll long long
#define ld long double
#define st string
#define dl double
#define wh while
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define tp tuple
#define ft first
#define sc second
#define ve vector
#define tos to_string
#define len length
#define rt return 0
#define br break
#define con continue
#define lcm(n, m) (n * m / gcd(n, m))
#define np next_permutation
#define repi(i, m, n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i, n) repi(i, 0, n)
#define repill(i, m, n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define repll(i, n) repill(i, 0, n)
#define revi(i, m, n) for(int i=(int)(m);i>(int)(n);i--)
#define rev(i, n) revi(i, 0, n)
#define revill(i, m, n) for(ll i=(ll)(m);i>(ll)(n);i--)
#define revll(i, n) revill(i, 0, n)
#define sz(v) ((int)(v).size()) 
#define each(i, n) for(auto&& i: n)
#define all(n) (n.begin(), n.end())
#define sp(n) cout << fixed << setprecision(n)
#pragma endregion
// sqrt ルート, int 2*10^9, gcd　最大公約数 __builtin_popcount bitの個数

int main() {
  int N;
  ci(N);
  rep(i, 10){
    if(i * 100 + i * 10 + i >= N){
      co(i * 100 + i * 10 + i);
      rt;
    }
  }
}

Measured memory_bytes: 256
import math
import queue
import bisect
import heapq
import time
import itertools

mod = int(1e9+7)

def swap(a,b):
    return (b,a)

def gcd(a,b): #最大公約数
    if (a<b):
        a,b = swap(a,b)
    if (b==0):
        return a
    else:
        return gcd(b,a%b)

def lcm(a,b): #最小公倍数
    return a/gcd(a,b)*b

def divisors(a): # 約数列挙
    divisors = []
    for i in range(1,int(a**0.5)+1):
        if a%i==0:
            divisors.append(i)
            if i!=a//i:
                divisors.append(a//i)
    return divisors

def is_prime(a): #素数判定
    if a<2:
        return False
    elif a==2:
        return True
    elif a%2==0:
        return False
    sqrt_num = int(a**0.5)
    for i in range(3,sqrt_num+1,2):
        if a%i==0:
            return False
    return True

def prime_num(a): #素数列挙
    pn = [2]
    for i in range(3,int(a**0.5),2):
        prime = True
        for j in pn:
            if i%j==0:
                prime = False
                break
        if prime:
            pn.append(i)
    return pn

def prime_fact(a): #素因数分解
    sqrt = math.sqrt(a)
    res = []
    i = 2
    if is_prime(a):
        res.append(a)
    else:
        while a!=1:
            while a%i==0:
                res.append(i)
                a //= i
            i += 1
    return res

def main():
    a,b,c = map(int,input().split())
    if a <= c and b >= c:
        print("Yes")
    else:
        print("No")
    return

if __name__=='__main__':
    main()


Measured memory_bytes: 38636
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <string>
#include <iostream>
#include <cassert>
#include <cmath>
using namespace std;

int main() {
        int a, b;
        scanf("%d %d", &a, &b);
        vector<vector<int>> d(a, vector<int> (b));
        for (int i = 0; i < a; i ++) { 
                for (int j = 0; j < b; j ++) {
                        scanf("%d", &d[i][j]);
                }
        }
        vector<vector<int>> f(110, vector<int> (110));
        for (int i = 0; i < 110; i ++) {
                for (int j = 0; j < 110; j ++) {
                        for (int k = 0; k < a; k ++) {
                                for (int l = 0; l < b; l ++) {
                                        f[i][j] = max(f[i][j], d[k][l] - (k + 1) * i - (l + 1) * j);
                                }
                        }
                }
        }
        for (int i = 0; i < a; i ++) {
                for (int j = 0; j < b; j ++) {
                        int f2 = 1 << 30;
                        for (int k = 0; k < 110; k ++) {
                                for (int l = 0; l < 110; l ++) {
                                        f2 = min(f2, f[k][l] + k * (i + 1) + l * (j + 1));
                                }
                        }
                        if (f2 != d[i][j]) {
                                puts("Impossible");
                                return 0;
                        }
                }
        }
        puts("Possible");
        printf("%d %d\n", 220, 109 + 109 + 110 * 110);
        for (int i = 0; i < 109; i ++) {
                printf("%d %d X\n", i + 1, i + 2);
        }
        for (int i = 0; i < 109; i ++) {
                printf("%d %d Y\n", i + 111, i + 112);
        }
        for (int i = 0; i < 110; i ++) {
                for (int j = 0; j < 110; j ++) {
                        printf("%d %d %d\n", i + 1, 220 - j, f[i][j]);
                }
        }
        printf("%d %d\n", 1, 220);
        return 0;
}



Measured memory_bytes: 384
#include<bits/stdc++.h>
#define F first
#define S second
#define MP make_pair
#define pb push_back
#define endl '\n'

using namespace std;

typedef long long LL;
typedef pair< int, int > P;
typedef pair< LL, LL > LP;
typedef pair< int, P > iP;
typedef pair< P, P > PP;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1000000007;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    set< int > st;
    int n;
    cin >> n;
    for( int i = 0; i < n; ++i ) {
        char c;
        cin >> c;
        st.insert( c );
    }

    if( st.size() == 3 ) cout << "Three";
    else cout << "Four";
    cout << endl;

    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<int>divisors(n + 2, 0);
    for(int i = 1; i <= n; i++){
        for(int j = i; j <= n; j = j + i){
            divisors[j]++;
        }
    }
    long long ans = 0;
    for(int i = 1; i < n; i++){
        ans = ans + 1LL * divisors[i];
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 7144
/*
Author: Srinjoy
Language: C++ 17
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define de(a) cout << #a << " = " << a << endl
#define dd(a) cout << #a << " = " << a << " "
#define optimiza_io cin.tie(0); ios_base::sync_with_stdio(0);
#define ZERO(a) memset(a,0,sizeof(a))
#define fileinput(s) freopen(s,"r",stdin)
#define MINUS(a) memset(a,0xff,sizeof(a))
typedef long long ll;
const ll mod = 1000000007;

template<class T>
istream& operator >> (istream& in, vector<T>& v){ for (auto &x : v) { in >> x; } return in; }
 
template<class T>
istream& operator >> (istream& in, pair<T, T> & v){ in >> v.fi >> v.se;return in; }

void printArr(vector<int> arr){
	cout<<"\n------------------------------------\n";

	for(int i=0;i<arr.size();i++) cout<<arr[i]<<" ";
	
	cout<<"\n------------------------------------\n";
}

void printArr(vector<vector<int> > arr){
	cout<<"\n------------------------------------\n";

	for(vector<int> i:arr){
		for(int j:i){
			cout<<j<<" ";
		}
		cout<<endl;
	}
	
	cout<<"\n------------------------------------\n";

}


void fill(vector<vector<ll>>& arr){
	for(int i=0;i<arr.size();i++){
		for(int j=0;j<arr[0].size();j++){
			arr[i][j]=-1;
		}
	}
}


ll solve(vector<ll>& arr, vector<ll> &arr1 , ll n , ll k , vector<vector<ll>>& dp){
	if(k<=0) return 0;
	if(n==0 && k>=0) return 1e12;

	if(dp[k][n]==-1)
		 dp[k][n] = min ( solve(arr,arr1,n-1,k,dp) ,  (arr1[n-1] + solve(arr,arr1,n,k-arr[n-1],dp) ) );

	return dp[k][n];
}



int main(){
	optimiza_io
	

	ll H,N;
	cin>>H>>N;

	vector<ll> wt(N);
	vector<ll> val(N);

	ll x,y;

	for(int i=0;i<N;i++){
		cin>>x>>y;
		wt[i]=x;
		val[i]=y;
	}


	vector<vector<ll>> dp;
	dp.assign(1e4+5,vector<ll>(1e3+2));

	fill(dp);



	ll ans = solve(wt,val,N,H,dp);


	cout<<ans<<endl;
	
}

Measured memory_bytes: 81024
#include <iostream>

using std::cin;
using std::cout;
using std::endl;

int main(){
	int a, b, c, d, r, l;

	cin >> a >> b >> c >> d;

	l = a + b;
	r = c + d;
	
	if (r > l)
		cout << "Right" << endl;
	else if (r < l)
		cout << "Left" << endl;
	else
		cout << "Balanced" << endl;
}	


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

int main() {

  string s;
  cin >> s;
  int n = s.size();
  
  if(s=="zyxwvutsrqponmlkjihgfedcba"){
    cout << -1 << endl;
    return 0;
  }
 
  int alp[26]={};
  rep(i,n) alp[s[i]-'a']++;
  
  rep(i,26){
    if(!alp[i]){
      cout << s +char('a'+i)<< endl;
      return 0;
    }
  }
  
  string t = s;
  next_permutation(s.begin(),s.end());
  string ans = "";
  rep(i,n){
    ans += s[i];
    if(s[i]>t[i])break;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a); i<(b); ++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int64_t i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define RANGE(a,b,c) (a).begin()+b,(a).begin()+c // コンテナ a の 要素 b から c へのイテレータ
#define MOD 1000000007
#define INF 1000000000000
typedef pair<int64_t, int64_t> PII;
typedef vector<int64_t> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

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

string S, T = ""; cin >> S;
int N = S.size();

int cnt = 0;
rep(i, 0, N){
    if (T == "" || S[i] == T.back()) T.push_back(S[i]);
    else {
        cnt += 2;
        T.pop_back();
    }
}
cout << cnt << endl;

}

// 書いて考える
// 境界，出力文字列 チェック
// 可読性優先．高速化次点．
// まずは全探索，分割統治，次にDP
// 制限を見る．境界に注意．求めたい量の変域．
// 偶奇，逆から，ソート，出現回数，出現位置，DP， 余事象，包除
// データ構造． 問題の特徴量．単調性，二分探索
// 存在判定：構成方法，入力の特徴
// gcd, lcm ,素因数分解．
// 例外を十分に含む一般化．想像力の限界
// 小さい系から例示
// 代数的処理
// 始めは過剰に例示・場合分けしてもいい．各場合を確実に対処．
// 自明な例から処理，除外．
// 小数のときは，精度の設定する．doubel 変数に数値を入力するときは 123. とする．
// テストケース作成は数表あり



Measured memory_bytes: 592
#include <iostream>
#include <map>
#include <algorithm>
#include <string>
#include <vector> 
#include <numeric>
#include <cmath>
#include <queue>
#include <iomanip>
#include <functional>

#define CHMAX(a,b) a = std::max(a,b)
#define CHMIN(a,b) a = std::min(a,b)
#define MAXMIN(a,b,c) std::max(a,min(b,c))
#define CHABS(a) a = std::abs(a) 
#define COUT(a) std::cout << a << std::endl
#define CERR(a) std::cerr << a << std::endl
#define FOR(n) for(lli i = 0; i < n; i++)

using namespace std;
using lli = long long int;
using pll = pair<lli, lli>;
using tlll = tuple<lli, lli, lli>;
using vll = vector<lli>;

lli mod197 = 1000000007LL;
lli INF = 10000000000000;

// ax + by = gcd(a,b) 最大公約数
template< typename T >
T extgcd(T a, T b, T& x, T& y) {
	T d = a;
	if (b != 0) {
		d = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	}
	else {
		x = 1;
		y = 0;
	}
	return d;
}


int main(void) {

	int n;
	string s;
	cin >> n >> s;

	for (char& c : s) {
		c = ((c - 'A') + n) % ('Z' - 'A' + 1) + 'A';
	}

	cout << s << endl;

	return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define IINF 10e8
#define INF 1<<30
#define MOD 1000000007
#define mod 10007
#define REP(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define REPE(i, a, n) for (ll i = a; i <= (ll)(n); i++)
#define Endl endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef pair<int,int>Pin;
typedef pair<ll,ll>Pll;
template<class T> using V=vector<T>;
long long GCD(long long a, long long b) {return b?GCD(b,a%b):a;}
long long LCM(long long a, long long b) {return a/GCD(a,b)*b;}
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int ddx[8]={-1,0,1,0,1,1,-1,-1};
int ddy[8]={0,-1,0,1,1,-1,1,-1};
ll cmp(pair<ll,ll>a,pair<ll,ll> b){
        if(a.se!=b.se)
        return a.se<b.se;
        else
        return a.fi<b.fi;
}
//----------------------------------------------------------------------
int n;
void call(int n){
  int i = 1;
 CHECK_NUM:
  int x = i;
  if ( x % 3 == 0 ){
    cout << " " << i;
    goto END_CHECK_NUM;
  }
 INCLUDE3:
  if ( x % 10 == 3 ){
    cout << " " << i;
    goto END_CHECK_NUM;
  }
  x /= 10;
  if ( x ) goto INCLUDE3;
 END_CHECK_NUM:
  if ( ++i <= n ) goto CHECK_NUM;

  cout << endl;
}
//----------------------------------------------------------------------
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------  
    //ll begin_time=clock();
    //------------------------------
    cin>>n;
    call(n);
    //-------------------------------  
    //ll end_time=clock();cout<<"time="<<end_time-begin_time<<"ms"<<endl;
    //-------------------------------
    return 0;
}
//----------------------------------------------------------------------


































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

int main() {
  string S; cin>>S;
  int N=S.size();
  bool ikeru=0;
  if(S.substr(0, 7)=="keyence") ikeru=1;
  if(S.substr(0, 6)=="keyenc" && S.substr(N-1, 1)=="e") ikeru=1;
  if(S.substr(0, 5)=="keyen" && S.substr(N-2, 2)=="ce") ikeru=1;
  if(S.substr(0, 4)=="keye" && S.substr(N-3, 3)=="nce") ikeru=1;
  if(S.substr(0, 3)=="key" && S.substr(N-4, 4)=="ence") ikeru=1;
  if(S.substr(0, 2)=="ke" && S.substr(N-5, 5)=="yence") ikeru=1;
  if(S.substr(0, 1)=="k" && S.substr(N-6, 6)=="eyence") ikeru=1;
  if(S.substr(N-7, 7)=="keyence") ikeru=1;
  
  if(ikeru) cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <algorithm>
#include <cmath>
#include <iomanip>
 
 
int main()
{
    std::string s; std::cin >> s;
    for(int i=0; i<s.length(); i++) std::cout << 'x';
    std::cout << "\n";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>

#define FOR(i, b, e) for(int i = (int)(b); i < (int)(e); ++i)
#define RFOR(i, b, e) for(int i = (int)(e-1); i >= 0; --i)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)
#define REPC(x,c) for(const auto& x:(c))
#define VS vector<string>
#define VI vector<int>
#define VVI vector<vector<int>>
#define ALL(x) (x).begin(),(x).end()
#define PAIR pair<int,int>
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

using  ll = long long;

using namespace std;


int main() {
	int h, w;
	cin >> h >> w;
	VVI mat;
	REP(h_, h) {
		VI v(w);
		REP(w_, w) {
			cin >> v[w_];
		}
		mat.emplace_back(v);
	}

	VVI output;
	int count = 0;
	REP(y, h) {
		REP(x, w) {
			if (mat[y][x] % 2 == 1) {
				if (y + 1 < h) {
					++mat[y + 1][x];
					output.push_back({ y + 1, x + 1, y + 2, x + 1 });
				} else if (x + 1 < w) {
					++mat[y][x + 1];
					output.push_back({ y + 1, x + 1, y + 1, x + 2 });
				} else {
					continue;
				}
				++count;
			}
		}
	}
	cout << count << endl;
	REPC(y, output) {
		cout << y[0] << " " << y[1] << " " << y[2] << " " << y[3] << endl;
	}
}

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

n, m = map(int, input().split())
fav = set(range(1, m+1))
for _ in range(n):
    a = set(list(map(int, input().split()))[1:])
    fav = fav.intersection(a)

print(len(fav))


Measured memory_bytes: 62404
#include <iostream>
#include <vector>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;

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

    if(n >= k) n %= k;
    cout << min(n, abs(n - k)) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using std::cout;
using std::cin;
using std::endl;

int main()
{
	int a, b;
	cin >> a >> b;
	cout << "a ";
	if (a > b) cout << "> ";
	if (a == b) cout << "== ";
	if (a < b) cout << "< ";
	cout << "b" << endl;
	return 0;
}

Measured memory_bytes: 1156
#include <bits/stdc++.h>
#define l_ength size
const int inf = (1<<30);
const int mod = 1000000007;
using ll = long long;
using namespace std;

int main(){
	char a, b; cin >> a >> b;
	if( a == 'H' && b == 'H' ) cout << 'H' << endl;
	if( a == 'D' && b == 'H' ) cout << 'D' << endl;
	if( a == 'D' && b == 'D' ) cout << 'H' << endl;
	if( a == 'H' && b == 'D' ) cout << 'D' << endl;
}

Measured memory_bytes: 384
#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<vector>
#include<string>
#include<string.h>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<cmath>
using namespace std;
typedef long long ll;
typedef long double ld;
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fr first
#define sc second
#define M 300010
int n,m,k,l,r,ans,a[10],c;
vector<int> v;
bool check(int x){
    while(x){
        if(a[x%10]) return false;
        x/=10;
    }
    return true;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>k;
        a[k]=1;
    }
    for(int i=n;;i++){
        if(check(i)) return cout<<i<<endl, 0;
    }
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<stdlib.h>
#include<iostream>
#include<sstream>
using namespace std;
int main(){
        double X,Y,N;
        char num[100]={0};
        while(scanf("%lf%lf%lf",&X,&Y,&N)!=EOF){
                int FLG=0,total=0,cnt=0;
                char W;
                sprintf(num,"%.15lf",X/Y);
                for(int i=0;;i++){
                        if(FLG==1){
                                W=num[i];
                                total+=atoi(&W);
                                cnt++;
                        }
                        if(cnt==N)break;
                        if(num[i]=='.')FLG=1;
                }
                printf("%d\n",total);
        }
        return 0;
}

Measured memory_bytes: 1252
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i < (int)(n); i++)
#define REP(i, m, n) for (int i = (m); i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define MOD 1000000007
#define INF (1e9)
#define PI (acos(-1))
#define mp make_pair
#define pb push_back
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl

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

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

template <class T> inline auto __lcm(T &a, T &b)
{ return a * b / __gcd(a, b); }


int main() {
    ll N;
    cin >> N;
    vector<ll> a(N);
    rep(i, N) {
        cin >> a[i];
    }

    ll cnt = 1;
    rep(i, N) {
        if (a[i] == cnt)
            ++cnt;
    }
    

    if (cnt == 1) {
        print(-1);
    } else {
        print(N - cnt + 1);
    }

    return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
int n;
struct point{int x,y;}a[90];
double jl(point a,point b){
   return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int main(){
  cin>>n;
  for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
  double ans=0;
  for(int i=1;i<=n;i++)
     for(int j=i+1;j<=n;j++)ans+=jl(a[i],a[j]);
  ans*=2;
  ans/=n;
  printf("%.6lf",ans);
  return 0;
}


Measured memory_bytes: 256
n, m = map(int, input().split())
h = list(map(int, input().split()))
links = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    links[a-1].append(b-1)
    links[b-1].append(a-1)

ans = 0
used = [0] * n
for i in range(n):
    if used[i]: continue
    used[i] = 1
    ok = True
    for to in links[i]:
        if h[to]>=h[i]: ok = False
        else: used[to] = 1
    if ok: ans += 1
print(ans)

Measured memory_bytes: 30220
#include <bits/stdc++.h>
#include <string.h>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(a) ((a)>(0)?(a):-(a))
#define rep(i,l,r) for((i)=(l);(i)<(r);(i)++)
using namespace std;
int main(){
    int a,b,ans;
    cin>>a>>b;
    ans=a+b;
    ans=max(ans,a-b);
    ans=max(ans,a*b);
    cout<<ans<<endl;
}

Measured memory_bytes: 256
/* by Natsu Kinmoe */
#include <bits/stdc++.h>
using namespace std;
#define SZ(x)               ((int)(x).size())
#define all(x)              (x).begin(), (x).end()
#define loop(i, n)          for(int i = 0; i < (n); i++)
#define cont(i, n)          for(int i = 1; i <= (n); i++)
#define circ(i, a, b)       for(int i = (a); i <= (b); i++)
#define range(i, a, b, c)   for(int i = (a); ((c) > 0 ? i <= (b) : i >= (b)); i += (c))
#define foreach(it, v)      for(__typeof((v).begin()) it = (v).begin(); it != (v).end(); it++)
#define y0          y0O0OO00OO0OO0OO0OOO00OO0OO0O0O000OO0
#define y1          y1II11II11III11I1III11II111IIII1II1I1
#define pub         push_back
#define pob         pop_back
#define mak         make_pair
typedef long long   ll;
typedef long double lf;
const int   Inf = 0x3f3f3f3f;
const ll    INF = 0x3f3f3f3f3f3f3f3fll;
/* Source code starts here */

int n;
ll ins[1 << 20];

int main() {
	cin >> n;
	cont(i, n) range(j, i, n, i) ins[j]++;
	ll ans = 0;
	cont(i, n - 1) ans += ins[i];
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 11388
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int N, L;
	cin >> N >> L;
	vector<string> ss;
	for(int i = 0; i < N; i++)
	{
		string s;
		cin >> s;
		ss.push_back(s);
				
	}

	sort(ss.begin(), ss.end());

	for (auto v : ss) cout << v;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
//const ll MOD = ;
ll mod(ll A, ll M) {return (A % M + M) % M;}
const ll INF = 1LL << 60;
template<class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
ll divceil(ll A, ll B) {return (A + (B - 1)) / B;}
ll myctoi(char C) {return C - '0';}
char myitoc(ll N) {return '0' + N;}
#define FINALANS(A) {cout << (A) << '\n'; exit(0);}

int main()
{
  ll N, T;
  cin >> N >> T;
  vector<pair<ll, ll>> AB(N);
  for (ll i = 0; i < N; i++)
  {
    cin >> AB.at(i).first >> AB.at(i).second;
  }
  sort(AB.begin(), AB.end());

  vector<vector<ll>> dp(3333, vector<ll>(6333, 0));
  for (ll i = 0; i < N; i++)
  {
    for (ll j = 0; j < 6300; j++)
    {
      chmax(dp.at(i + 1).at(j), dp.at(i).at(j));

      if (j < T)
        chmax(dp.at(i + 1).at(j + AB.at(i).first), dp.at(i).at(j) + AB.at(i).second);
    }
  }

  ll ans = 0;
  for (ll i = 0; i < 6300; i++)
  {
    chmax(ans, dp.at(N).at(i));
  }
  cout << ans << endl;
}


Measured memory_bytes: 165376
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=5e18;

int main() {
  string s;
  cin >> s;
  ll n=s.size();
  ll res=inf;
  for(ll i=0;i<n-2;i++) {
    ll tmp=0;
    for(ll j=0;j<3;j++) {
      tmp*=10;
      tmp+=(s[i+j]-'0');
    }
    res=min(res,abs(753-tmp));
  }
  cout << res << endl;
}

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

class Solution
{
    static long CalcEnergy(int order, long distance)
    {
        int coef = 5;
        if (order > 0)
        {
            coef = 2 * order + 3;
        }

        return coef * distance;
    }

    static void Main()
    {
        var vals = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
        var N = vals[0];
        var X = vals[1];
        var xs = Console.ReadLine().Split(' ').Select(long.Parse).OrderByDescending(t => t).ToArray();

        var maxK = (int)Math.Ceiling(N / 2.0);
        var accum = new long[N + 1];
        long acc = 0;
        for (int i = 0; i < N; i++)
        {
            acc += xs[i];
            accum[i + 1] = acc;
        }

        decimal min = decimal.MaxValue;
        for (int k = 1; k <= maxK; k++)
        {
            decimal energy = (k + N) * X;
            for (int i = 0; i < N; i += k)
            {
                var j = Math.Min(N, i + k);
                var order = i / k;
                energy += CalcEnergy(order, accum[j] - accum[i]);
            }

            min = Math.Min(energy, min);
        }

        Console.WriteLine(min);
    }
}

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

#define ms(a, v) memset(a, v, sizeof(a))
#define sfor(i, n) for (int i = 1; i <= n; ++i)
#define tfor(i, n) for (int i = 0; i < n; ++i)
using namespace std;
using ll = long long;

#ifdef GONGKUNPENG
#define MAXN 20
#else
#define MAXN 100005
#endif

int main() {
  int k, a, p, t = 0, r = 1;
  scanf("%d", &k);
  if ((k & 1) && (k % 5)){
    if (7 % k) {
      if(k % 7 == 0) k /= 7;
      t = 1;
      p = 10 % k;
      while(t %= k) {
        t = t * p + 1;
        ++r;
      }
      printf("%d\n", r);
    }
    else printf("1\n");
  }
  else printf("-1\n");
  return 0;
}

Measured memory_bytes: 3808
#include <iostream>
#include <vector>

int N;

void countingSort(std::vector<int>& A, std::vector<int>* B, int k) {
  std::vector<int> C(k + 1, 0);

  for (int j = 0; j < N; ++j)
    C[A[j]]++;

  for (int i = 1 ; i <= k; ++i)
    C[i] = C[i] + C[i-1];

  for (int j = N - 1; j >= 0; --j) {
    (*B)[C[A[j]]] = A[j];
    C[A[j]]--;
  }
}

int main() {
  std::cin >> N;
  std::vector<int> A;
  int max = 0;
  for (int i = 0; i < N; ++i) {
    int a;
    std::cin >> a;
    max = (a > max) ? a : max;
    A.push_back(a);
  }
  std::vector<int> B(N + 1);
  countingSort(A, &B, max);
  for (int i = 1; i <= N; ++i) {
    std::cout << B[i] << (i == N ? "\n" : " ");
  }
  return 0;
}

Measured memory_bytes: 18488
#include <cstdio>
#include <iostream>
#include <string>
#include <stack>
#include <cmath>

#define loop(i,a,b) for(int i = a; i < b; i++)
#define rep(i,a) loop(i,0,a)
using namespace std;

int S(int N){
  int ans=0;
  while(N!=0){
    ans+=(N%10);
    N/=10;
  }
  return ans;
}


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

  int M = (int)(N/2) +2;

  int sum=1000000;

  loop(i,2,M){
    int tmp = S(i)+S(N-i);
    if(tmp<sum) sum = tmp;
  }

  cout<<sum<<endl;

  return 0;
}


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

int main() {
    int H,W,a[3000],b[3000];
    int j=0;
    
	while(cin>>H>>W){
	    if(H==0 && W ==0){
	        break;
	    }

	char result;
	a[j] = H;
	b[j] = W;
	
    for(int k=0;k<a[j];k++){
      string ret = "";
      for(int i=0;i<b[j];i++) 
      if(i==0 ||i==W-1 || k==0||k==H-1){
      ret += "#";
      }
      else{
          ret += ".";
      }
      cout << ret << endl;

    }
    cout<<endl;
    j++;
	}
	return 0;
}


Measured memory_bytes: 3120
#include<iostream>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<algorithm>
#include<cstring>
#include<string>
#include<cassert>
#include<cmath>
#include<climits>
#include<iomanip>
#include<stack>
#include<unordered_map>
#include<bitset>
#include<limits>
using namespace std;
#define MOD 1000000007
#define rep(i,m,n) for(int (i)=(int)(m);i<(int)(n);i++)
#define REP(i,n) rep(i,0,n)
#define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i)
#define ll long long
typedef pair<ll, ll> P;
const long long INF = 1LL << 60;
const long double EPS = 1e-10;

template<class T> inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T> inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
ll cost;
struct Edge {
	ll src;
	ll dest;
	ll weight;
	bool rev;
	Edge(ll f, ll t, ll w, bool r)
	{
		src = f;
		dest = t;
		weight = w;
		rev = r;
	}
};
struct Vertex {
	ll no;
	ll point;
	ll visitedCnt;
	bool cango;
	Vertex() {
		int i = 0;
	}
	Vertex(ll n, ll p) {
		no = n;
		point = p;
		visitedCnt = 0;
		cango = false;
	}
	bool operator < (const Vertex& v2) const {
		return this->point < v2.point;
	};
};
class Graph {
private:
public:
	map<ll, Vertex> vmap;
	map<ll, vector<Edge>> emap;
	vector<Edge> edges;
	Graph() {
	}
	void addEdge(ll src, ll dest, ll weight, bool rev) {
		if (vmap.count(src) == 0) {
			Vertex vf(src, 0);
			vmap[src] = vf;
		}
		if (vmap.count(dest) == 0) {
			Vertex vf(dest, 0);
			vmap[dest] = vf;
		}
		Edge e(src, dest, weight, rev);
		emap[src].push_back(e);
		edges.push_back(e);
	}

	void checkEdge(ll no) {
		if (vmap[no].cango) return;
		vmap[no].cango = true;
		REP(i, emap[no].size()) {
			Edge& e = emap[no][i];
			checkEdge(e.dest);
		}
	}
	ll BellmanFord() {
		vmap[0].point = 0;
		for (int i = 1; i < (int)vmap.size(); i++) {
			vmap[i].point = -INF;
		}
		for (int i = 0; i < (int)vmap.size() - 1; i++) {
			bool updated = false;
			for (int k = 0; k < (int)edges.size(); k++) {
				Edge& e = edges[k];
				Vertex& u = vmap[e.src];
				Vertex& v = vmap[e.dest];
				ll getPoint = u.point + e.weight - cost;
				if (v.point < getPoint) {
					v.point = getPoint;
					updated = true;
				}
			}
			if (!updated) {
				break;
			}
		}

		REP(k, edges.size()) {
			Edge& e = edges[k];
			Vertex& u = vmap[e.src];
			Vertex& v = vmap[e.dest];
			if (v.point == -INF) continue;
			ll pp = u.point + e.weight - cost;
			if (pp > v.point) {
				return -1;
			}
		}

		Vertex& vg = vmap[vmap.size() - 1];
		if (vg.point < 0) return 0;
		return vg.point;
	}
};

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

	ll n, m, p;
	cin >> n >> m >> p;
	cost = p;
	Graph g;
	Graph rg;
	REP(i, m) {
		ll a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		g.addEdge(a, b, c, false);
		rg.addEdge(b, a, c, false);
	}
	g.checkEdge(0);
	rg.checkEdge(n - 1);

	Graph newg;
	REP(i, n) {
		if (!g.vmap[i].cango || !rg.vmap[i].cango) {
			continue;
		}
		REP(k, g.emap[i].size()) {
			newg.addEdge(g.emap[i][k].src, g.emap[i][k].dest, g.emap[i][k].weight, false);
		}
	}
	ll ret = newg.BellmanFord();

	cout << ret << endl;

	return 0;
}


Measured memory_bytes: 2808
import java.math.*
import java.util.*
import java.util.function.*
import java.util.stream.*
import kotlin.math.min

fun main(args: Array<String>) {
  val sc = Scanner(System.`in`)
  val n = sc.nextInt()
  val m = sc.nextInt()
  val list = (0 until n).map {
    UnionFind(it)
  }
  (0 until m).forEach {
    val a = sc.nextInt() - 1
    val b = sc.nextInt() - 1
    UnionFind.union(list[a], list[b], ::min)
  }
  println(list.map(UnionFind<Int>::getGroupValue).toSet().size - 1);
}

/**
 * Union Find
 * @param <T> 値の型
</T> */
internal class UnionFind<T>(
  /** 値  */
  val value: T
) {
  /** 親 (なければnull)  */
  private var parent: UnionFind<T>? = null
  /**
   * この要素の値を返す。
   * @return 値
   */

  /** 所属するグループの合算した値 (root要素以外のgroupValueは正しいとは限らない)  */
  private var groupValue: T
  override fun equals(o: Any?): Boolean {
    return this === o
  }

  /**
   * root要素を返す。
   * @return root要素
   */
  private val root: UnionFind<T>
    private get() {
      if (parent == null) {
        return this
      }
      val root = parent!!.root
      parent = root
      return root
    }

  /**
   * この要素が属するグループの値を返す。
   * @return グループの値
   */
  fun getGroupValue(): T {
    return root.groupValue
  }

  companion object {
    /**
     * 同じグループに属するかどうか
     * @param a a
     * @param b b
     * @param <S> 値の型
     * @return 同じグループに属するならtrue
    </S> */
    fun <S> sameGroup(a: UnionFind<S>, b: UnionFind<S>): Boolean {
      return a.root == b.root
    }

    /**
     * 同じ木に所属させる
     * @param a a
     * @param b b
     * @param <S> 値の型
    </S> */
    fun <S> union(a: UnionFind<S>, b: UnionFind<S>) {
      union(a, b, { _1, _ -> _1 })
    }

    /**
     * 同じ木に所属させる。また、値の計算もする
     * @param a a
     * @param b b
     * @param groupValueFunction aとbが異なるグループに属するとき、その2つのグループの値を合算する関数。
     * @param <S> 値の型
    </S> */
    fun <S> union(a: UnionFind<S>, b: UnionFind<S>, groupValueFunction: (S, S) -> S) {
      val aRoot = a.root
      val bRoot = b.root
      if (aRoot != bRoot) {
        bRoot.parent = aRoot
        aRoot.groupValue = groupValueFunction(aRoot.groupValue, bRoot.groupValue)
      }
    }
  }

  /**
   * Union Find
   * @param value 値
   */
  init {
    groupValue = value
  }
}


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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()

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

  int a,b;
  cin>>a>>b;
  if(a<0){
    if(b<0)cout<<(((b-a+1)%2)?"Negative":"Positive")<<endl;
    else cout<<"Zero"<<endl;
  }
  else if(a==0){
    cout<<"Zero"<<endl;
  }
  else if(a>0){
    cout<<"Positive"<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Queue;
import java.util.Scanner;


public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int n= sc.nextInt();
		int m = sc.nextInt();
		
		HashMap<Integer, HashSet<Integer>> map = new HashMap<>();
		int[] inDegree = new int[n];
		for (int i=0;i<m;i++) {
			int x = sc.nextInt()-1;
			int y = sc.nextInt()-1;
			if (!map.containsKey(x)) {
				map.put(x, new HashSet<Integer>());
			}
			map.get(x).add(y);
			inDegree[y]++;
		}
		//topological sort
		ArrayList<Integer> sorted = new ArrayList<>();
		ArrayDeque<Integer> q = new ArrayDeque<>();
		for (int i=0;i<n;i++) {
			if (inDegree[i]==0) {
				q.add(i);
			}
		}
		while (!q.isEmpty()) {
			int first = q.poll();
			sorted.add(first);
			if (map.get(first) != null) {
				for (Integer to : map.get(first)) {
					inDegree[to]--;
					if (inDegree[to] == 0) {
						q.add(to);
					}
				}
			}
		}
		
		int[] dp = new int[n];
		
		for (Integer v : sorted) {
			if (map.get(v) != null) {
				for (Integer to : map.get(v)) {
					dp[to] = Math.max(dp[to], dp[v]+1);
				}
			}
		}
		int ans = 0;
		for (int i=0;i<n;i++) {
			ans = Math.max(ans, dp[i]);
		}
		System.out.println(ans);
	}

}


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

int main(){
    int n, pos;
    string str;

    cin >> n; cin.get();
    while (n--){
	getline(cin, str);
	while (pos = str.find("Hoshino"), pos!= string::npos)
	    str.replace(pos,7,"Hoshina");
	cout << str << "\n";
    }
}

Measured memory_bytes: 0