akhauriyash/Code-Regression huggingface dataset:
#ifndef DEBUG
#    pragma GCC optimize("O3,no-stack-protector")
#    pragma GCC optimize("unroll-loops")

#    if __cplusplus < 201703L
#        pragma GCC target("avx")
#    else
#        pragma GCC target("avx2")
#    endif

#endif

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define dump(x) cout << x << endl
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REP(i, n) for (int i = 0, i##_len = (n); i <= i##_len; ++i)
#define rep3(i, l, r) for (int i = l, i##_len = (r); i < i##_len; ++i)
#define REP3(i, l, r) for (int i = l, i##_len = (r); i <= i##_len; ++i)
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
typedef int64_t Int;
typedef long double Ld;

using namespace std;
using Graph = vector<vector<Int>>;

const Ld pi = M_PI;
const Int MOD = 1000000007;
const Int INF = 1LL << 62;

Int Floor(Int a, Int b) {
    return (a - (a % b)) / b;
}

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

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

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

    Int n;
    cin >> n;
    vector<Int> a(n), b(n);
    for (Int i = 0; i < n; i++) {
        cin >> a[i];
        b[i] = a[i];
    }
    for (Int i = 1; i < n; i++) {
        b[i] += b[i - 1];
        b[i] %= MOD;
    }

    Int ans = 0;
    for (Int i = 0; i < n - 1; i++) {
        Int tem = b.back() - b[i];
        if (tem < 0) {
            tem += MOD;
        }

        ans += a[i] * tem;
        ans %= MOD;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 6360
#include <bits/stdc++.h>
  using namespace std;
  long long MOD=1000000007;
  #define IOS() ios_base::sync_with_stdio(0); cin.tie(0);
  typedef long long ll;
  #define pb push_back
  typedef pair<ll,ll> pi;
  ll dp[4000][4000]={0ll};
  ll a[4000];

ll find (int i, int j)
{
	if(i==j)
		return a[i];
	if(dp[i][j]!=0)
		return dp[i][j];



	dp[i][j]=std::max(a[i]-find(i+1,j),a[j]-find(i,j-1));
	return dp[i][j];
}



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

 	for (int i = 0; i < n; ++i)
 	{
 			dp[i][i]=a[i];
 	}

 	cout<<find(0,n-1)<<endl;
  return 0;
}

Measured memory_bytes: 51220
n = gets.to_i
k = gets.to_i
x_array = gets.split(' ')
sum = 0
x_array.each do |v|
    v = v.to_i
	if(v > k or k < v*2)
    	sum += (k-v).abs * 2
    else
    	sum += v * 2
    end
end
print sum


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

int main()
{
	int cnt[4] = {};
	int n;
	string s;
	while(cin >> n){
		cin.ignore();
		cin >> s;
		if(s == "A")cnt[0]++;
		if(s == "B")cnt[1]++;
		if(s == "AB")cnt[2]++;
		if(s == "O")cnt[3]++;
	}
	for(int i = 0; i < 4; ++i){
		cout << cnt[i] << endl;
	}
}

Measured memory_bytes: 1204
package main

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

func main() {
	N := getStdinInt()
	a := getStdinIntArr()
	cnt := 0
	for i := 0; i < N; i++ {
		if a[i]%2 == 1 && (i+1)%2 == 1 {
			cnt++
		}
	}
	fmt.Printf("%d\n", cnt)
}

var sc = bufio.NewReaderSize(os.Stdin, 1024*1024*10)

func getStdin() string {
	return readLine()
}
func getStdinInt() int {
	str := getStdin()
	rtn, _ := strconv.Atoi(str)
	return rtn
}
func getStdinInt2() (int, int) {
	list := getStdinIntArr()
	return list[0], list[1]
}
func getStdinInt3() (int, int, int) {
	list := getStdinIntArr()
	return list[0], list[1], list[2]
}
func getStdinInt64() int64 {
	str := getStdin()
	rtn, _ := strconv.ParseInt(str, 10, 64)
	return rtn
}
func getStdinInt64_2() (int64, int64) {
	list := getStdinIntArr64()
	return list[0], list[1]
}
func getStdinInt64_3() (int64, int64, int64) {
	list := getStdinIntArr64()
	return list[0], list[1], list[2]
}
func getStdinIntArr() []int {
	str := getStdin()
	list := strings.Split(str, " ")
	rtn := make([]int, len(list))
	for idx, val := range list {
		rtn[idx], _ = strconv.Atoi(val)
	}
	return rtn
}
func getStdinIntArr64() []int64 {
	str := getStdin()
	list := strings.Split(str, " ")
	rtn := make([]int64, len(list))
	for idx, val := range list {
		rtn[idx], _ = strconv.ParseInt(val, 10, 64)
	}
	return rtn
}
func readLine() string {
	buf := make([]byte, 0, 0)
	for {
		l, p, _ := sc.ReadLine()
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}


Measured memory_bytes: 2168
n = int(input())
s = list(input())
mod = 10 ** 9 + 7
alpha = "abcdefghijklmnopqrstuvwxyz"
cnt = []
for a in alpha:
    tmp = s.count(a)
    cnt.append(tmp + 1)
ans = 1
for num in cnt:
    ans *= num
    ans %= mod
print(ans - 1)

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

int main(){
  
  int N;
  cin >> N;
  
  vector<int> order(N);
  rep(i,N) cin >> order.at(i);
  vector<int> menu(N);
  rep(i,N) cin >> menu.at(i);
  vector<int> addNum(N-1);
  for(int i = 0; i < N-1; i++) cin >> addNum[i];
  
  int sums = 0;
  rep(i,N){
    sums += menu[order[i]-1];
    if (i < N-1 &&  order[i]+1 == order[i+1]) {
      sums += addNum[order[i]-1];
    }
  }
  cout << sums << endl;
  return 0;
}


Measured memory_bytes: 256
import sys 
N, K = map(int, input().split())
H = list(map(int, input().split()))

INF = sys.maxsize

DP = [INF] * N

for i in range(N):
    for k in range(1, K+1):
        if DP[i] < INF:
            DP[i] = min(abs(H[i] - H[max(i - k, 0)]) + DP[max(i - k, 0)], DP[i])
        else:
            DP[i] = abs(H[i] - H[max(i - k, 0)]) + (DP[max(i - k, 0)] if DP[max(i - k, 0)]  != INF else 0)
        

print(DP[N-1])


Measured memory_bytes: 52576
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

ans = 0

for i in range(N):
  if A[i] < B[i]:
    ans = ans + A[i] + min(B[i]-A[i], A[i+1])
    A[i+1] = max(0, A[i+1]-(B[i]-A[i]))
  else:
    ans = ans + B[i]
    
print(ans)

Measured memory_bytes: 18624
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>

using namespace std;

constexpr int p = 1e9+7;

int N;
int dp[100008];

int main() {
    int K, a;
	scanf("%d%d", &N, &K);
    {
        scanf("%d", &a);
        for(int k=0; k<=a; ++k) {
            dp[k] = 1;
        }
    }
    for(int n=1; n<N; ++n) {
        for(int k=1; k<=K; ++k) {
            dp[k] += dp[k-1];
            if(p<=dp[k]) dp[k] -= p;
        }
        scanf("%d", &a);
        for(int k=K; a<k; --k) {
            dp[k] -= dp[k-a-1];
            if(dp[k]<0) dp[k] += p;
        }
    }
    printf("%d\n", dp[K]);
	return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
const int inf = 1001001001;

int main(){
  char c;
  cin >> c;

  char C = toupper(c);

  cout << (C == c ? "A":"a") << endl;

}


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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define fst first
#define snd second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define EPS (1e-9)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

bool LT(double a,double b) { return !equals(a,b) && a < b; }
bool LTE(double a,double b) { return equals(a,b) || a < b; }

const string YES = "";
const string NO  = "";

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

void solve() {

}

int main() {
  ll x;
  cin >> x;
  ll v = 100;
  int cnt = 0;
  while( !LTE(x,v) ) {
    v = v + (ll)(v * 0.01);
    ++cnt;
  }
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 3640
"""Boot-camp-for-Beginners_Easy003_B_Qualification-simulator_19-August-2020.py"""
N, A, B = map(int, input().split())
S = str(input())

RANK_a = 0
RANK_b = 0

for i in range(N):
    if S[i] == "a":
        if RANK_a+RANK_b < A+B:
            RANK_a += 1
            print("Yes")
        else:
            print("No")
    elif S[i] == "b":

        if RANK_a+RANK_b < A+B:
            if RANK_b < B:
                RANK_b += 1
                print("Yes")
            else:
                print("No")
        else:
            print("No")
    else:
        
        print("No")


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

int cntDistincts(int n)
{
	long long int start = 1;
	int ret = 0;
	while(true)
	{
		long long int total = (start*(start+1))/2;
		if(total <= n)
		{
			++ret;
		}
		else
			break;
		++start;
	}
	return ret;
}

int main()
{
	long long int n; cin >> n;
	long long int p = 2;
	int ans = 0;
	for(; p*p <= n; ++p)
	{
		if((n%p) == 0)
		{
			int cnt = 0;
			while((n%p) == 0)
			{
				n /= p;
				++cnt;
			}
			ans += cntDistincts(cnt);
		}
	}
	if(n!= 1) ++ans;

	cout << ans;

	return 0;
}

Measured memory_bytes: 3640
using System;
using CompLib.Util;

public class Program
{
    public void Solve()
    {
        var sc = new Scanner();
        int n = sc.NextInt();
        int k = sc.NextInt();
        long ans = 1;
        ans *= k;
        for (int i = 0; i < n-1; i++)
        {
            ans *= (k - 1);
        }

        Console.WriteLine(ans);
    }

    public static void Main(string[] args) => new Program().Solve();
}

namespace CompLib.Util
{
    using System;
    using System.Linq;

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}

Measured memory_bytes: 11092
while True:
	try:
		ans = []
		n = int(raw_input())
		for b in [512,256,128,64,32,16,8,4,2,1]:
			if n >= b:
				n -= b
				ans.append(b)
		ans.reverse()
		ans = map(str,ans)
		ans = ' '.join(ans)
		print ans
	except:
		break

Measured memory_bytes: 4228
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>

using namespace std;

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

	vector<int> H(N);
	for (int i = 0; i < N; i++) {
		cin >> H.at(i);
	}

	if (K >= N) {
		cout << 0 << endl;
		return 0;
	}

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

	long long res = 0;
	for (int i = 0; i < N - K; i++)
	{
		res += H.at(i);
	}

	cout << res << endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <fstream>
#include <string>
#include <math.h>
#include <cstdlib>
#include <istream>
#include <sstream>
#include <cctype>
#define fore(i,x,y) for(long long i=x;i<y;i++)
typedef long long ll;
using namespace std;
int main()
{
	char X,Y;
	cin >> X >> Y;
	if((int)X<(int)Y){
		cout << "<" << endl;
	}
	else if((int)X>(int)Y){
		cout << ">" << endl;
	}
	else{
		cout << "=" << endl;
	}

}

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

div = make_divisors(M)

ans = 0
for x in div:
    if x*N <= M:
        ans = max(ans, x)

print(ans)

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

int main()
{
        int N, M;
        cin >> N >> M;
        vector<bool> S(N, false);
        vector<bool> F(N, false);
        for (int i = 0; i < M; ++i) {
                int a, b;
                cin >> a >> b;
                if (a == 1) {
                        S[b-1] = true;
                }
                if (b == N) {
                        F[a-1] = true;
                }
        }

        for (int i = 0; i < N; ++i) {
                if (S[i] == true && F[i] == true) {
                        cout << "POSSIBLE" << endl;
                        exit(0);
                }
        }
        cout << "IMPOSSIBLE" << endl;
}


Measured memory_bytes: 256
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

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

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

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{BinaryHeap, HashMap};

#[allow(dead_code)]
type Graph = Vec<Vec<usize>>;

fn main() {
    input! {
        n: usize,
        a: [i64; n],
    }
    let mut ans = 1 << 50;
    let mut sum = vec![0];
    for i in 0..a.len() {
        let v = a[i] + *sum.last().unwrap();
        sum.push(v);
    }
    let mut j = 0;
    let mut k = 0;
    for i in 2..n - 1 {
        while j + 1 < i {
            if (sum[i] - 2 * sum[j]).abs() > (sum[i] - 2 * sum[j + 1]).abs() {
                j += 1;
            } else {
                break;
            }
        }
        while k <= i {
            k += 1
        }
        while k + 1 < n {
            let s = sum[n] - sum[i];
            if (s - 2 * (sum[k] - sum[i])).abs() > (s - 2 * (sum[k + 1] - sum[i])).abs() {
                k += 1;
            } else {
                break;
            }
        }
        let mut v = vec![];
        v.push(sum[j]);
        v.push(sum[i] - sum[j]);
        v.push(sum[k] - sum[i]);
        v.push(sum[n] - sum[k]);
        // println!("{}, {}, {}, {}", j, i, k, n);

        // println!(
        //     "{}, {}, {}, {}",
        //     sum[j],
        //     sum[i] - sum[j],
        //     sum[k] - sum[i],
        //     sum[n] - sum[k]
        // );
        ans = min(ans, v.iter().max().unwrap() - v.iter().min().unwrap());
    }

    println!("{}", ans);
}


Measured memory_bytes: 8444
from heapq import heappush, heappop

def solve():
    N, M = map(int , input().split())
    arbeit_A_B = list(list(map(int , input().split())) for _ in range(N))
    arbeit_A_B = sorted(arbeit_A_B, key=lambda x: (x[0], -x[1]))
    # print(arbeit_A_B)
    day = 1
    result = 0
    index_arbeit = 0
    heap_q = []
    while day <= M:
        while index_arbeit < N:
            A,B = arbeit_A_B[index_arbeit]
            if A <= day:
                heappush(heap_q, (-1)*B)
            else: break
            index_arbeit += 1
            
        if heap_q:
            result -= heappop(heap_q)
        day += 1
            
    print(result)
    
solve()

Measured memory_bytes: 39388
N, M = map(int, input().split())
a_list = list(map(int, input().split()))
written_nums = []

for i in range(M):
    b, c = map(int, input().split())
    written_nums.append((c, b))

a_list = sorted(a_list)
written_nums = sorted(written_nums, reverse = True)

append_list = []
for c, b in written_nums:
    append_list += [c for _ in range(b)]

    if len(append_list) >= N:
        break
append_list.sort(reverse = True)


total = sum(a_list)
max_total = total
for i in range(min(N, len(append_list))):
    total -= a_list[i]
    total += append_list[i]
    max_total = max(max_total, total)

print(max_total)


Measured memory_bytes: 23112
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1145141919810893364
typedef pair<int,int> PP;
typedef long long ll;
#define int ll
#define setdouble setprecision
#define REP(i,n) for(int i=0;i<(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define GOODBYE cout << -1 << endl;return 0
#define Endl endl

signed main(void){
    int N,X;
    cin >> N >> X;
    int Ans=N;
    
    int a=N-X,b=X;
    if(a>b)swap(a,b);
    while(1){
        
        Ans+=2*a*((int)(b/a)-1);
        b=a+b%a;
        if(a==1){
            Ans+=2*b-1;
            break;
        }
        if(a==b){
            Ans+=a;
            break;
        }
        Ans+=2*a;
        b-=a;
        if(a>b)swap(a,b);
        
        if(a==1){
            Ans+=2*b-1;
            break;
        }
    }
    cout << Ans << endl;
    return 0;
}





Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <stack>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <cctype>
using namespace std;
typedef long long ll;
const int MAXN = 1e5+10;
ll a[MAXN],b[MAXN];
int main()
{
    ll ans = 0;
    int N;
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
    {
        scanf("%lld %lld",a+i,b+i);
    }
    for(int i=N;i>=1;i--)
    {
        ll v = ((a[i]+ans)%b[i]);
        if(v==0) continue;
        ans+=b[i]-v;
    }
    printf("%lld\n",ans);
	return 0;
}



Measured memory_bytes: 1792
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
int f(string str) {
	set < string > s;
	s.insert(str);
    while (1) {
    	int ok = 0;
    	for (auto it : s) {
    		for (int i = 0;i + 1 < it.length();++i) {
    			if (it[i] != it[i + 1]) {
    				string ss = it;
    				for (char c = 'a';c <= 'c';++c)
    					if (ss[i] != c && ss[i + 1] != c) {
    						ss[i] = ss[i + 1] = c;
    						break;
    					}
    				if (!s.count(ss))
    					ok = 1;
    				s.insert(ss);
    			}
    		}
    	}
    	if (!ok)
    		break;
    }
    return s.size();
}
const int N = 5e5;
int dp[N][3][3][2];
const int mod = 998244353;
void add(int & x,int y) {
	x = (x + y) % mod;
}
int main(void)
{
	string str;
	cin>>str;
	if (str.length() <= 3)
		cout << f(str) << '\n';
	else {
		int ok = 1;
		for (auto it : str)
			ok &= it == str[0];
		if (ok) {
			cout << "1\n";
			return 0;
		}
		int sum = 0;
		for (auto it : str)
			sum += (it - '0');
		sum %= 3;
		for (int i = 0;i < 3;++i)
			dp[1][i][i][0] = 1;
		int n = str.length();
		for (int i = 1;i < n;++i)
			for (int prev = 0;prev < 3;++prev)
				for (int sm = 0;sm < 3;++sm)
					for (int nw = 0;nw < 3;++nw)
						for (int eq = 0;eq < 2;++eq)
							add(dp[i + 1][nw][(sm + nw) % 3][eq | (nw == prev)],dp[i][prev][sm][eq]);
		int ans = 0;
		for (int t = 0;t < 3;++t)
			add(ans,dp[n][t][sum][1]);
		int cnt = 1;
		for (int i = 0;i + 1 < n;++i)
			cnt &= str[i] != str[i + 1];
		(ans += cnt) %= mod;
		cout << ans << '\n';
	}
    return 0;
}

Measured memory_bytes: 14852
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;


int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<vector<pair<int,int>>> graph(n);

    for (int i = 0; i < m; ++i) {
        int l, r, d;
        cin >> l >> r >> d;
        --l, --r;
        graph[l].emplace_back(r, d);
        graph[r].emplace_back(l, -d);
    }


    vector<bool> visited(n, false);
    const long long INF = 1LL << 50;
    vector<long long> dis(n, INF);
    vector<int> que(n + 123);

    bool ok = true;

    long long LIMIT = 1e9;
    for (int i = 0; i < n && ok; ++i) {
        if (visited[i]) {
            continue;
        }

        int s = i;
        int sz = 0;
        que[sz++] = s;
        visited[s] = true;
        dis[s] = 0;

        for (int j = 0; j < sz && ok; ++j) {
            int u = que[j];
            for (auto& e : graph[u]) {
                int v = e.first;
                long long w = e.second;
                long long d = dis[u] + w;
                if (!visited[v]) {
                    visited[v] = true;
                    dis[v] = d;
                    que[sz++] = v;
                } else {
                    if (d != dis[v]) {
                        ok = false;
                        break;
                    }
                }
            }
        }

        long long mn = INF;
        long long mx = -INF;
        for (int j = 0; j < sz; ++j) {
            int v = que[j];
            mn = min(mn, dis[v]);
            mx = max(mx, dis[v]);
        }
        if ((mx - mn) > LIMIT) {
            ok = false;
        }
    }

    if (!ok) {
        cout << "No\n";
    } else {
        cout << "Yes\n";
    }


    return 0;
}

Measured memory_bytes: 9984
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); ++i)
using namespace std;
using ll=long long;
int main(){
    int n;
    cin>>n;
    vector<int>a(n);
    rep(i,n)cin>>a[i];
    sort(a.rbegin(),a.rend());
    int cnt1=0,cnt2=0;
    rep(i,n){
        if(i%2==0)cnt1+=a[i];
        else cnt2+=a[i];
    }
    cout<<cnt1-cnt2<<endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main { 
    public static void main(String[] args) {
      Scanner scanner = new Scanner(System.in);
      String inputStr = scanner.nextLine();
      int inputStrSize = inputStr.length();
      
      String before = "";
      String after = "";
      if (inputStrSize % 2 == 0) {
      	int splitPoint = inputStrSize / 2;
        before = inputStr.substring(0, splitPoint);
        after = inputStr.substring(splitPoint);
       	after = stringReverce(after);
      } else {
        int splitPoint = inputStrSize / 2;
        before = inputStr.substring(0, splitPoint);
        after = inputStr.substring(splitPoint + 1);
		after = stringReverce(after);
      } 
      	System.out.println(judgeCount(before, after));
    }
  
  	public static String stringReverce(String str) {
      StringBuffer sb = new StringBuffer(str);
      return sb.reverse().toString();
    }
  
  	public static int judgeCount(String str1, String str2) {
      int cnt = 0;
      int size = str1.length();
      for (int i = 0; i < size; i++) {
		if (!(str1.charAt(i) == str2.charAt(i))) {
        	cnt++;
        }
      }
      return cnt;
    }

}

Measured memory_bytes: 21972
#include<bits/stdc++.h>
#include<vector>
#include<string>
#define rep(i,a,b) for(long long int i=(a);i<(b);i++)
#define se(a) a.begin(),a.end()
#define ll unsigned long long int
#define mll map<ll,ll>
#define pll pair<ll, ll>
#define pii pair<int,int>
#define pb push_back
#define mk make_pair
#define F first
#define S second
#define mod 1000000007
#define maxn 100005
#define inf 1e18
#define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
int main()
{
	boost;
	ll n,m;
	cin>>n>>m;
	ll a[n][m];
	rep(i,0,n)
	rep(j,0,m)
	{
		char ch;
		cin>>ch;
		if(ch=='.')
		a[i][j]=1;
		else
		a[i][j]=0;
	}
	ll dp[n][m];
	memset(dp,0,sizeof(dp));
	dp[0][0]=1;
	rep(i,1,n)
	if(a[i][0])
	dp[i][0]=dp[i-1][0];
	rep(i,1,m)
	if(a[0][i])
	dp[0][i]=dp[0][i-1];
	rep(i,1,n)
	rep(j,1,m)
	if(a[i][j])
	dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;
	cout<<dp[n-1][m-1]%mod<<endl;
}

Measured memory_bytes: 15872
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <stack>
#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<ll, ll>;
using Graph = vector<vector<int>>;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
#define rep(i, N) for(int i = 0; i < N; i++)
#define rep2(i, l, r) for (ll i = (ll)l; i < (ll)(r); i++)
#define INF 1000000000000000000
#define MAX 200001
#define MOD 1000000007

template <typename T > inline string toString(const T &a) {ostringstream oss; oss << a; return oss.str();};

int main(){
    string s;
    cin >> s;
    ll m[] = {1, 10, 9, 12, 3, 4};
    reverse(s.begin(), s.end());
    vector<vector<ll>> dp(s.size() + 1, vector<ll>(13, 0));
    if(s[0] == '?'){
        for(int i = 0; i < 10; i++) dp[0][i] = 1;
    }
    else{
        ll D = s[0] - '0';
        dp[0][D] = 1;
    }
    for(int i = 1; i < s.size(); i++){
        if(s[i] == '?'){
            for(int j = 0; j < 10; j++){
                int amari = j * m[i % 6] % 13;
                for(int k = 0; k < 13; k++){
                    dp[i][(k + amari) % 13] += dp[i - 1][k];
                    dp[i][(k + amari) % 13] %= MOD;
                }
            }
        }
        else{
            int D = s[i] - '0';
            ll amari = D * m[i % 6] % 13;
            for(int j = 0; j < 13; j++){
                dp[i][(j + amari) % 13] += dp[i - 1][j];
                dp[i][(j + amari) % 13] %= MOD;
            } 
        }
    }
    cout << dp[s.size()-1][5] << endl;
}

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

divisors = []
for r in range(1, int(N**0.5)+1):
    if N % r == 0:
        divisors.append(r)
        if r != N // r:
            divisors.append(N//r)

ans = 0
for r in divisors:
    m = N//r - 1
    if m > 0 and N // m == N % m:
        ans += m
print(ans)

Measured memory_bytes: 40300
import math
from itertools import combinations
from collections import defaultdict

# from math import gcd
import fractions

A, B = list(map(int, input().split()))

def make_prime_list(num):
    if num < 2:
        return []

    # 0のものは素数じゃないとする
    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0 # 1は素数ではない
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break

        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0

    return [prime for prime in prime_list if prime != 0]

def prime_factorization(num):
    if num <= 1:
        return False
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list(num_sqrt)

        dict_counter = defaultdict(int)
        for prime in prime_list:
            while num % prime == 0:
                dict_counter[prime] += 1
                num //= prime
        if num != 1:
            dict_counter[num] += 1

        dict_counter = dict(dict_counter)

        return dict_counter

if A >= B:
    A, B = B, A

# # 小さい方の約数リストを計算
# divA = []
# for i in range(1, A // 2 + 1):
#     if A % i == 0:
#         divA.append(i)
# divA.append(A)
# div = [n for n in divA if B % n == 0]
# Ndiv = len(div)

# print(div)
# for n in div:
#     for m in div:
#         if n < m and fractions.gcd(n, m) == 1:
#             print(n, m)

# 深さ優先探索
# def dfs(i, S, d):
#     selected = div[i]
#     S.add(selected)
#     depth = d
#     for j in range(i + 1, Ndiv):
#         if fractions.gcd(div[i], div[j]) == 1:
#             flag = True
#             for k in S:
#                 if fractions.gcd(k, div[j]) != 1:
#                     flag = False
#                     break
#             if flag:
#                 dj = dfs(j, S, d + 1)
#                 depth = max(depth, dj)
#     return depth

# ans = dfs(0, set({}), 1)
# print(Ndiv + 1)

lA = prime_factorization(A)
lB = prime_factorization(B)

if not lA or not lB:
    print(1)
    exit()

count = 0
for key in lA:
    if key in lB:
        count += 1
print(count + 1)

Measured memory_bytes: 134948
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <cmath>

using namespace std;

int main()
{
    string a,b,c;
    int pok=0;
    int a1=-1,b1=-1,c1=-1;
    cin >> a;
    cin >> b;
    cin >> c;
    while (true)
    {
        if (pok==0)
        {
            a1++;
            if (a1==a.size())
            {
                cout << "A" << endl;
                return 0;
            }
            if (a[a1]=='a')
                pok=0;
            else if (a[a1]=='b')
                pok=1;
            else if (a[a1]=='c')
                pok=2;
        }
        else if (pok==1)
        {
            b1++;
            if (b1==b.size())
            {
                cout << "B" << endl;
                return 0;
            }
            if (b[b1]=='a')
                pok=0;
            else if (b[b1]=='b')
                pok=1;
            else if (b[b1]=='c')
                pok=2;
        }
        else
        {
            c1++;
            if (c1==c.size())
            {
                cout << "C" << endl;
                return 0;
            }
            if (c[c1]=='a')
                pok=0;
            else if (c[c1]=='b')
                pok=1;
            else if (c[c1]=='c')
                pok=2;
        }
    }

    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <ctime>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
#include <queue>
#include <utility>
#include <cmath>
using namespace std;

long n;

int main(){
	scanf("%ld", &n);
	for(long a = 1; a <= 3500; a++){
		for(long b = 1; b <= 3500; b++){
			if(4*a*b - n*a - n*b != 0 && (n * a * b) % (4*a*b - n*a - n*b) == 0 && (n*a*b) / (4*a*b - n*a - n*b) > 0){
				printf("%ld %ld %ld\n", a, b, (n*a*b) / (4*a*b - n*a - n*b));
				return 0;
			}
		}
	}
}

Measured memory_bytes: 256
//nani?
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include <ext/pb_ds/detail/standard_policies.hpp>
#define pi acos(-1);
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define f(i,a,b) for( int i = a; i < b ; i++ ) 
#define sor(a) sort( a.begin(), a.end() )
#define rsor(a) sort( a.rbegin(), a.rend() )
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
//#define inf 1LL<<62
typedef long long ll;
typedef double ld;
using namespace std;
const ll inf=1e10;
const ll MOD=1e9+7;
const ll mod=998244353;
// ac cmtr;
const ll MAX_N = 1e5+5;
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cout << name << " : " << arg1 << endl;}
 
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cout.write(names, comma - names) << " : " << arg1<<" | ";
  __f(comma+1, args...);}
#else
#define trace(...)
#endif
//---------------------------


int main(){
    fastio;
    ll n,m;
    cin>>n>>m;
    ll ans= n*(n-1)/2 + m*(m-1)/2;
    cout<<ans<<endl;


}



Measured memory_bytes: 256
import math
import itertools
import sys
input = sys.stdin.readline

def main():
    D, G = map(int, input().split())
    spc_list = [[(i+1) * 100] + [int(v) for v in input().split()] for i in range(D)]
    max_scores = [spc[0] * spc[1] + spc[2] for spc in spc_list]
    min_q = float("inf")
    for q_list in itertools.permutations(list(range(D))):
        score = 0
        q_num = 0
        for q_idx in q_list:
            if score + max_scores[q_idx] < G:
                score += max_scores[q_idx]
                q_num += spc_list[q_idx][1]
            else:
                q_num += min(math.ceil((G-score) / spc_list[q_idx][0]), spc_list[q_idx][1])
                score = G
                """
                for _ in range(spc_list[q_idx][1]):
                    score += spc_list[q_idx][0]
                    q_num += 1
                    if score >= G:
                        break
                score += spc_list[q_idx][2]
"""
            if score >= G:
                break
        if q_num < min_q:
            min_q = q_num
    print(min_q)


if __name__ == '__main__':
    main()


Measured memory_bytes: 42504
#include <cmath>
#include <cstdio>
#include <vector>
#include <list>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stack>
#include <fstream>
#include <queue>
#include <iomanip>
#include <iterator>
#include <map>
#include <unordered_map>
#include <set>
#define fast ios_base::sync_with_stdio(false)
#define ll long long int
#define ld long double
#define vi vector<ll>
#define vvi vector<vi >
#define pi pair<ll,ll>
#define vvpi vector<vector<pi > >
#define vpi vector<pi >
#define vppi vector<pair<ll,pi > >
#define vs vector<string>
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define eb emplace_back
#define mkp make_pair
#define fs first
#define se second
#define crz(v,n) v.clear(),v.resize(n+1,0)
#define print(v) for(ll it=0;it<v.size();it++) cout<<v[it]<<" ";cout<<endl
#define printp(v) for(ll it=0;it<v.size();it++) cout<<v[it].first<<" "<<v[it].second<<endl
using namespace std;
int main(){
	ll n,i,j,s=1e18;cin>>n;vi v(n);for(i=0;i<n;i++) cin>>v[i];
	for(i=1;i<101;i++){ll c=0;
		for(j=0;j<n;j++) c+=pow(v[j]-i,2);
		s=min(s,c);
	}cout<<s<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>

#define REP(i,b,n) for(int i=b;i<n;i++)
#define REPR(i,b,n) for(int i=n-1;i>=b;i--)
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define NCLR(mat) memset(mat, -1, sizeof(mat))
#define EACH(i, c) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define BIT(n, b) ((n>>b) & 1)
#define PI acos(-1.0)

using namespace std;

static const double EPS = 1e-9;
typedef long long ll;
typedef pair<int, int> paii;

int N;
paii flo[128][128];
int vis[128][128];

int dfs(int x, int y, int id){
	
	if(vis[y][x] != 0){
		return vis[y][x];
	}
	else{
		vis[y][x] = id;
		return vis[y][x] = dfs(flo[y][x].first, flo[y][x].second, id);
	}
}

int solve(){
	
	int res = 0, id = 1;
	CLR(vis);
	
	for(int y=0; y<N; ++y){
		for(int x=0; x<N; ++x){
			
			if(vis[y][x]==0)
				res += (id == dfs(x, y, id));
			
			id++;
		}
	}
	
	return res;
}

int main(){
	
	while(cin >> N, N){
		
		for(int y=0; y<N; ++y){
			for(int x=0; x<N; ++x){
				cin >> flo[y][x].first >> flo[y][x].second;
			}
		}
		
		cout << solve() << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1360
import numpy as np
n,x = map(int,input().split())
li = list(map(int,input().split()))
li.sort()
res = np.cumsum(li)
cnt=0
if res[-1] == x:
    cnt = len(res)
elif res[-1] > x:
    for i in res:
        if i <= x:
            cnt += 1
        else:
            break
else:
    cnt = len(res) -1
print(cnt)

Measured memory_bytes: 12504
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using ll = long long;
int main() {
	int N;
	cin >> N;
	vector<long long int>a(N);
	for (int i = 0; i < N; ++i) {
		cin >> a.at(i);
	}
	sort(a.begin(), a.end());
	reverse(a.begin(), a.end());
	int count = 1;
	int flag = 0;
	long long int b = 0, c = 0;
	for (int i = 1; i < N; ++i) {
		if (a.at(i - 1) != a.at(i)) {
			count = 1;
			continue;
		}
		else count++;
		if (count == 2 && flag == 0) {
			b = a.at(i);
			flag = 1;
			continue;
		}
		if (count == 4) {
			c = a.at(i);
			break;
		}
		if (count == 2 && flag == 1) {
			c = a.at(i);
			break;
		}
	}
	long long int ans = b * c;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
#define REP(i,s,N) for(ll i=s;i<N;++i)

int main() {
	ll N, K;
	cin >> N >> K;
	vector<ll> A(N,0);
	REP(i,0,N) scanf("%lld", &A[i]); 

	// A1 A2 A3 ... AN
	// 1  2  3      N の permutation
	// K個の連続値を選べる.選ぶと, その中の最小値で置換される.	
	// 何回選べば統一できるか.
	//
	// 1. KでN個を塗りつぶす. それだけ...ではない. 選ぶ順番も考慮する必要がある.
	// 1 2 3 4 5, K=2 ならば, 左から順に選んでいく.
	// 5 - 2 + 1 = 4回
	// N - K + 1 が解.
	// 結局すべてを1にすることになる.
	// 1の位置次第で回数が変わる.
	// 3 4 1 2 5, K=2
	// K=2 => 4 = (N - K + 1)
	// K=3 => 2 = (N - K) 
	// K=4 => 2 = (N - K + 1)
	// K=5 => 1
	// 6 5 4 1 2 3
	// K=2 => left = 3, right = 2 : 5
	// K=3 => left = 2, right = 1 : 3
	// K=4 => left = 1, right = 1 : 2
	// K=5 => 2
	// K=6 => 1
	// 6 5 4 2 1 3 
	// K = 3 => left = 2, right = 1 : 3 
	// K = 4 => left = 2, right = 1 : 3 ????  誤り. 答えは2
	// ... 考え方 ... min(left, right) < Kなので, まず N - K で1回, 残り N - K + 1箇所(端は1)をKで埋め尽くす. 
	// もしくは N - K(1を含まない) を K-1の塗りで埋め尽くす.
	// 端が1, N < K の場合の塗りつぶし回数は, (N + K - 1)/ K 
	// ex. N = 5, K = 3 答えは2 (5 + 3 - 1) / 3 = 2
	//
	// 7 6 5 4 3 1 2
	// K = 3 => 3.   (7 - 3 + 1)/3 = 2
	// 次のパターンに対応しないといけない
	// 10 4
	// 2 3 4 5 1 6 7 8 9 10
	// これは5 1 6 7 をまず対象とするのが解で3になる.
	// 次のパターンにも同時に対応しないといけない
	// 10 3            
	// 2 3 4 5 1 6 7 8 9 10
	// これは5が解.

  ll idx = -1;
	REP(i,0,N) {
		if (A[i] == 1) {
			idx = i;
			break;
		}
	}	
	// left count, right count, including 1
	ll left, right;
	left = idx + 1;
	right = N - left + 1;
	ll minlr = min(left, right);
	// K < min(left, right) : N - K + 1 
	// min(left, right) < K < max(left, right) : 
	// max(left, right) < K :
	
	ll ans = 0;
	if (N == K) {
		ans = 1;
	} else if (K < minlr) {
		if ((minlr-1) % (K-1) == 0) {
			//cout << "here" << endl;
			ans = (left-1+K-2)/(K-1) + (right-1+K-2)/(K-1); 
		} else {
			ll res = N - K;
			ans = 1 + res/(K-1);
		}
	} else {
		ll res = N - K + 1;
		ans = 1 + (res + K - 2)/(K-1);
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 1024
#include <iostream>
#include <math.h>
#include <string>

using namespace std;
int main()
{
    string s,t,u;
    int a,b;
    cin>>s>>t>>a>>b>>u;

    if(s == u){
        a--;
    }
    else{
        b--;
    }
    cout<<a<<" "<<b<<" "<<endl;
    return 0;
}

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

int main() {
    int n;
    int m;
 
   cin >> n >> m;
  
   int a[n][2],b[m][2];
  
   for(int i = 0;i<n;i++){
     
      for(int ii = 0;ii<2;ii++){

        cin >> a[i][ii];
        
      }
     
   }
  
   for(int k = 0;k<m;k++){
     for(int kk = 0;kk<2;kk++){
       
       cin >> b[k][kk];
       
     }
   }
  
   int ans[n];
  
  
   for(int j = 0;j<n;j++){
     
     
     int ansnum = m+1;
     
     int minsum = 1000000000;
     
     for(int v = 0;v<m;v++){
       
          int sum = 0;
       
          for(int jj = 0;jj<2;jj++){
          
      
              // cout << a[j][jj] << "|"<< b[v][jj] <<endl;
          
                int t = a[j][jj] - b[v][jj];
                if(t<0){
                  t = -t;
                }
                
                sum = sum + t;
           }
       
          
         //  cout << sum <<endl;
       
          if(sum < minsum){
            
            minsum = sum;
            
            ansnum = v+1;
            
          }
        }
     
     // cout << "ans:"<<ansnum <<endl;
     cout <<ansnum <<endl;
   }
  
  // for(int v = 0;v<m;v++){
   //  for(int vv = 0;vv<m;vv++){
   
   //    cout << b[v][vv] << endl;

    // }
  // }
  
  // cout << n << endl;
  // cout << m << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
char s[20][20];
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	int cnt = 0;
	for (int i = 0; i < n; ++ i) {
		scanf("%s", s[i]);
		for (int j = 0; j < m; ++ j) if (s[i][j] == '#') cnt ++;
	}
	puts(cnt == n + m - 1 ? "Possible" : "Impossible");
}



Measured memory_bytes: 256
import java.io.*;
import java.util.*;

class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        double a = Double.parseDouble(st.nextToken());
        System.out.printf("%.6f ",a*a*Math.PI);
        System.out.printf("%.6f\n",a*2*Math.PI);
    }
}

Measured memory_bytes: 24696
def main():
    N,M = map(int,input().split())
    ABC = [list(map(int,input().split())) for _ in [0]*M]

    E = [{} for _ in [0]*N]
    Eb = [{} for _ in [0]*N]
    for a,b,c in ABC:
        E[a-1][b-1] = -c
        Eb[b-1][a-1] = -c

    #0 -> N-1 経路上にない頂点を除く
    V1 = [False]*N
    V1[0] = True
    q = [0]
    qp = q.pop
    qa = q.append
    while q:
        i = qp()
        for j in E[i]:
            if V1[j]:continue
            qa(j)
            V1[j]=True
    V2 = [False]*N
    V2[-1] = True
    qa(N-1)
    while q:
        i = qp()
        for j in Eb[i]:
            if V2[j] or not V1[j]:continue
            qa(j)
            V2[j]=True
    for i in range(N):
        if V1[i] and V2[i]:continue
        for j in Eb[i]:
            E[j].pop(i)

    INFTY = 10**18
    d = [INFTY]*N
    d[0] = 0

    def update():
        done = [False]*N
        done[0] = True
        q = [0]
        qp = q.pop
        qa = q.append
        while q:
            i = qp()
            di = d[i]
            for j,c in E[i].items():
                d[j] = min(d[j],d[i]+c)
                if not done[j]:
                    qa(j)
                    done[j] = True

    for _ in range(N-1):update()
    dc = d[:]
    update()
    if dc!=d:
        print("inf")
    else:
        print(-d[-1])
main()

Measured memory_bytes: 4440
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <cctype>
using namespace std;

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)

int n;
string in;

string i2s(int i) {
  stringstream ss;
  ss << i;
  return ss.str();
}

void solve() {
  string prev(in.begin(), in.end());
  rep (i,n) {
    string next;
    char c = '\0';
    int cnt = 0;    
    rep (j,prev.size()) {
      if (c != prev[j]) {
        if (cnt) {
          next += i2s(cnt);
          next += c;
        }
        cnt = 1;
        c = prev[j];
      } else { cnt++; }
    }
    if (cnt) { next += i2s(cnt); next += c; }
    prev.assign(next.begin(), next.end());
  }
  cout<<prev<<endl;
}

int main() {
  while (cin>>n, n) {
    cin>>in;
    solve();
  }
  return 0;
}

Measured memory_bytes: 0
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		try (Scanner sc = new Scanner(System.in)) {
			int r, D, a = 0;
			r = sc.nextInt();
			D = sc.nextInt();
			a = sc.nextInt();

			for (int i = 1; i <= 10; i++) {
				int cal = r*a - D;
				System.out.println(cal);
				a = cal;
			}
		} catch (Exception e) {
			// TODO: handle exception
		}
	}
	
}


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

int main() {
int a,b,c; cin>>a>>b>>c;
  if(b/a>=c) cout<<c<<endl;
  else cout<<b/a<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#define rep(i,n) for(int i=0;i<(n);i++)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define psortfirst(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.first<b.first;});
#define All(x) (x).begin(),(x).end()
using namespace std;
using pii  = pair<int,int>;
long long gcd(long long a, long long b){return (b == 0 ? a : gcd(b, a%b));}
long long lcm(long long a, long long b){return a*b/gcd(a,b);}
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
int BinarySearch(int key,int n,int S[]){
  int l=0,r=n;
  while(r-l>1){
    int mid=(l+r)/2;
    if(S[mid]>key)r=mid;
    else l=mid;
  }
  return S[l]==(key?1:0);
}
typedef long long ll;
#define MOD 1000000007
#define EPS 10e-8

ll row[107],col[107];

int main() {
  ll H,W;cin >> H >> W;
  char A[107][107];
  rep(i,H){
    rep(j,W){
      cin >> A[i][j];
      if(A[i][j]=='#'){
        row[i]++;
        col[j]++;
      }
    }
  }
  rep(i,H){
    if(row[i]>0){
      rep(j,W){
        if(col[j]>0){
          cout << A[i][j];
        }
      }
      cout << endl;
    }
  }
}

Measured memory_bytes: 256
import java.util.Scanner;

/**
 * ABC111A
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String n = sc.next();
        n = n.replace("1", "a").replace("9", "b").replace("a", "9").replace("b", "1");
        System.out.println(n);
        sc.close();
    }
}

Measured memory_bytes: 21844
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;

int main(void){
        int i,j,k;
        int n;
        int x[100];
        int a[3][3];
        bool b[3][3];
        bool ans = false;
        for(i=0;i<3;i++){
                scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]);
        }
        scanf("%d", &n);
        for(i=0;i<n;i++){
                scanf("%d", &x[i]);
        }
        for(i=0;i<3;i++){
                for(j=0;j<3;j++){
                        b[i][j] = false;
                }
        }
        for(i=0;i<3;i++){
                for(j=0;j<3;j++){
                        for(k=0;k<n;k++){
                                if(a[i][j]==x[k]){
                                        b[i][j] = true;
                                }
                        }
                }
        }
        
        for(i=0;i<3;i++){
                if(b[i][0]==true && b[i][1]==true && b[i][2]==true){
                        ans = true;
                }
        }
        for(j=0;j<3;j++){
                if(b[0][j]==true && b[1][j]==true && b[2][j]==true){
                        ans = true;
                }
        }
        if(b[0][0]==true && b[1][1]==true && b[2][2]==true){
                ans = true;
        }
        if(b[0][2]==true && b[1][1]==true && b[0][2]==true){
                ans = true;
        }
        
        if(ans){
                printf("Yes\n");
        } else {
                printf("No\n");
        }
        return 0;
}



Measured memory_bytes: 256