akhauriyash/Code-Regression huggingface dataset:
S = input()
K = int(input())
p = -1
for i in range(len(S)):
    if S[i] == "1":
        p = i
    else:
        break
if K <= p + 1:
    print(1)
elif p < 0:
    print(S[0])
else:
    print(S[p+1])


Measured memory_bytes: 3060
open System

// prelude
let readStr () = stdin.ReadLine()

let readInt () = stdin.ReadLine() |> int
let readInts () = stdin.ReadLine().Split() |> Array.map int

let pair = function
| [|a; b|] -> (a, b)
| _ -> failwith "owatta"

let triple = function
| [|a; b; c|] -> (a, b, c)
| _ -> failwith "owatta"

let inc n = n + 1
let dec n = n - 1

let inline flip f a b = f b a
let rec fix f = fun x -> (f (fix f)) x

module Option =
  let getOr defaultValue = function
  | Some x -> x
  | None -> defaultValue

module Array =
  let modify (arr: _ []) i f =
    arr.[i] <- f arr.[i]

module Array2D =
  let modify (arr: _ [,]) i j f =
    arr.[i, j] <- f arr.[i, j]

// start
let S = readStr().ToCharArray()

match S.[2] = S.[3] && S.[4]=S.[5] with
| true -> "Yes"
| false -> "No"
|> printfn "%s"


Measured memory_bytes: 13916
#include<bits/stdc++.h>
using namespace std;
void func(int y,int x);
int dy[4]={0,1,0,-1};
int dx[4]={1,0,-1,0};
char MAP[13][13];
int main(void){
	int i,j;
	while(1){
		for(i=0;i<12;i++){
			for(j=0;j<12;j++){
				cin>>MAP[i][j];
			}
		}
		if(cin.eof())	break;
		
		/* for(i=0;i<12;i++){
			for(j=0;j<12;j++){
				cout<<MAP[i][j];
			}
			cout<<endl;
		} */
		int cnt=0;
		for(i=0;i<12;i++){
			for(j=0;j<12;j++){
				if(MAP[i][j]=='1'){
					cnt++;
					MAP[i][j]='0';
					func(i,j);
				}
			}
		}
		cout<<cnt<<endl;
	}
	return 0;
}
void func(int y,int x){
	int i;
	int yy,xx;
	for(i=0;i<4;i++){
		yy=y+dy[i];
		xx=x+dx[i];
		if(0<=yy&&yy<12&&0<=xx&&xx<12&&MAP[yy][xx]=='1'){
			MAP[yy][xx]='0';
			func(yy,xx);
		}
	}
}


Measured memory_bytes: 3016
import java.util.* 
fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val S = sc.next()
    var max = 0
    var count = 0
    for (c in S) {
        if (c == 'A' || c == 'T' || c == 'G' || c == 'C') count++
        else {
            if(max < count) max = count
            count = 0
        }
    }
    if (max < count) max = count
    println(max)
}


Measured memory_bytes: 31400
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(sc.hasNext()){
			int n = sc.nextInt();
			if(n==0)break;
			int sum = 0;
			int count = 0;
			int num = 0;
			for(int i=5;i<=n;i+=5){
				count = 0;
				num = i;
				while(num%5==0){
					num /= 5;
					count++;
				}
				sum += count;
			}
				
			System.out.println(sum);
		}
	
	}	
}

Measured memory_bytes: 17180
#include <cstdio>

int main(void) {
    int H, W;
    scanf("%d %d", &H, &W);
    char c[H+1][W+1];
    for(int i=1 ; i<=H ; i++) {
        scanf("%s", c[i]);
    }
    for(int i=1 ; i<=H ; i++) {
        printf("%s\n", c[i]);
        printf("%s\n", c[i]);
    }
    return 0;
}


Measured memory_bytes: 128
// 
// w配列に対して, k, Pを決めて, 輸送可能な量を求める.
// 輸送可能量がWの総和以上となる最小のPを求める.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
using ll = long long;

// そもそもこの機能が難しい...
// greedyに求められないように思う...
// greedyに求められない場合にどうしたらいいのか分からない
// 全探索は場合の数が多すぎる...はず...
// 答えを見る... 解説を改めて詳しく読み直す...
// truckの台数 k もinputにするらしい
// するとgreedyに求めることができる...ということだが, これがピンとこない.
//
ll get_maximum_total_weights(const vector<ll> &w, ll k, ll P) {
	ll stacking_weight = 0;
	ll total_weight = 0;
	for(ll i=0;i<w.size();++i) {
		if(stacking_weight + w[i] <= P) {
			stacking_weight += w[i];
		} else {
			k--;
			if (k==0 || w[i] > P) break;
			stacking_weight = w[i];
		}
		total_weight += w[i];
	}
	return total_weight;
}

ll binary_search(const vector<ll> &w, ll k, ll left, ll right) {
	ll sum_of_weights = accumulate(w.begin(), w.end(), 0LL);
	ll mid;  
	// caution!
	// 間に必ず1を開けるようにしている
	while (right - left > 1) { 
		mid = (left + right) / 2;
		ll loadable_weights = get_maximum_total_weights(w, k, mid);
		//cout << left << ", " << mid << ", " << right << ": " << loadable_weights << endl;
		if (loadable_weights >= sum_of_weights) {
			right = mid;
		} else {
			left  = mid;// right - left > 1なので, midはleftよりも大きい
		}
	}
	// このrightはかならず loadable_weights >= sum_of_weights を満たす.
	return right;
}

int main() {
	int n,k;
	cin >> n >> k;
	vector<ll> w(n,0);
	for(ll i=0;i<n;++i) cin >> w[i]; 
	cout << binary_search(w, k, 0, 10000 * 1e5) << endl;
	return 0;
}



Measured memory_bytes: 3616
n,a = map(int, raw_input().split())
ais = map(int, raw_input().split())
mem = {}
def dfs(i,ais, cumul,count,a):
	if i == len(ais):
		return 1 if (count > 0 and count * a == cumul) else 0
	if (i,cumul,count) in mem:
		return mem[(i,cumul,count)]
	mem[(i,cumul,count)] = dfs(i+1, ais, cumul + ais[i], count +1, a) + dfs(i+1, ais, cumul, count, a)
	return mem[(i,cumul,count)]
print dfs(0,ais,0,0,a)

Measured memory_bytes: 174108
#include <bits/stdc++.h>
using namespace std;
using V = vector<int>;
using P = pair<int, int>;
#define rep(i, n) for(int i=0; i<int(n); ++i)


// 有向グラフの接続行列 B に対し，線形方程式 Bx = c を (必要なら mod 2 で) 解くライブラリ
template<typename T>
struct LinearSystemIncidence {
  struct Edge {
    int id, to; bool fwd;
    Edge(int i, int t, bool f) : id(i), to(t), fwd(f) {}
  };

  int n, m;
  bool mod2;
  vector<T> x;
  vector<bool> seen;
  vector<vector<Edge>> G;
  
  LinearSystemIncidence(int n, vector<P> &E, bool mod2=false) : n(n), m(E.size()), G(n), mod2(mod2) {
    rep(i, m) {
      G[E[i].first].emplace_back(i, E[i].second, true);
      G[E[i].second].emplace_back(i, E[i].first, false);
    }
  }

  T dfs(vector<T> &b, int u) {
    seen[u] = true;
    T res = b[u];
    for (Edge e : G[u]) {
      if (seen[e.to]) continue;
      T tmp = dfs(b, e.to);
      if (e.fwd) x[e.id] = tmp;
      else x[e.id] = -tmp;
      res += tmp;
      if (mod2) {
        x[e.id] %= 2;
        if (x[e.id] < 0) x[e.id] += 2;
      }
    }
    if (mod2) res %= 2;
    return res;
  }

  pair<bool, vector<T>> solve(vector<T> &b) {
    x.assign(m, 0);
    seen.assign(n, false);
    rep(u, n) {
      if (seen[u]) continue;
      if (dfs(b, u)) return {false, vector<T>()};
    }
    return {true, move(x)};
  }
};


int main() {
  int n, m; cin >> n >> m;
  vector<P> E;
  V c(n+1);
  rep(i, m) {
    int u, v; cin >> u >> v;
    E.emplace_back(u, v);
    c[u] ^= 1;
  }

  LinearSystemIncidence<int> LSI(n+1, E, true);
  auto sol = LSI.solve(c);

  if (sol.first) {
    rep(i, m) {
      if (sol.second[i]) swap(E[i].first, E[i].second);
      cout << E[i].first << " " << E[i].second << "\n";
    }
  }
  else cout << -1 << "\n";
  return 0;
}

Measured memory_bytes: 11764
n,z,w = map(int, input().split())
 
x = z
y = w

a = list(map(int, input().split()))
if len(a) == 1:
    ans= abs(a[0] - w)
else:
    ans = max(abs(a[n-2] - a[n-1]), abs(a[n-1] - w))

print(ans)


Measured memory_bytes: 3188
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0,i##_len=int(n);i<i##_len;++i)
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define All(x) (x).begin(),(x).end()
#define rAll(x) (x).rbegin(),(x).rend()
using namespace std;
using ll = long long;

int main(){
    int N;cin>>N;
    vector<int> a(N+1);
    REP(i, N) cin >> a[i+1];
    vector<int> ans(N+1);
    int M=0;
    for(int i=N;i>0;--i){
        int t=0;
        for(int j=2*i;j<=N;j+=i){
            t+=ans[j];
        }
        ans[i]=(t+a[i])&1;
        M+=ans[i];
    }
    cout<<M<<endl;
    bool flag=false;
    REP(i,N) if(ans[i+1]){
        cout<<(flag?" ":"")<<i+1;
        flag=true;
    }
    cout<<endl;
}


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

int main() {
  long N;
  cin >> N;
  vector<long> A(N);
  for (long i = 0; i < N; i++) cin >> A.at(i);
  sort(A.rbegin(), A.rend());
  long ans = A.at(0);
  for (long i = 2; i < N; i++) {
    ans += A.at(i / 2);
  }
  cout << ans << "\n";
}

Measured memory_bytes: 4840
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;cin>>n;
  double a[n],d[n],ans=0;
  for(int i=0;i<n;i++){
    cin>>a[i],d[i]=a[i];
    for(int j=0;j<i;j++){
      double x=fabs(a[i]-a[j]),y=a[i]+a[j];
      d[i]=max(d[i],d[j]+sqrt(y*y-x*x));
    }
    ans=max(ans,d[i]+a[i]);
  }
  printf("%.9f\n",ans);
}


Measured memory_bytes: 1252
s=input().split()
k,n=int(s[0]),int(s[1])
s=[]
a=input().split()

for i in range(0,n):
  
  if(i == n-1):
    s.append(abs(k-int(a[i])+int(a[0])))
  else:
  	s.append(abs(int(a[i])-int(a[i+1])))
print(k-max(s))
  
 
  



Measured memory_bytes: 20148
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class Main{

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

	Scanner scan;
	private int N,count;
	private boolean loop,inf;
	private List<Order> OrderList;
	private Map<Integer,Integer> LineNumber,infLine;
	private HashMap<String,Integer> Var;

	private void mainrun() {
		scan = new Scanner(System.in);

		N = Integer.parseInt(scan.nextLine());
		loop = true;
		inf = false;

		OrderList = new ArrayList<>();
		LineNumber = new HashMap<>();
		Var = new HashMap<>();
		infLine = new HashMap<>();

		for(int i = 0;i < N ;i++) {
			String[] line = scan.nextLine().split(" ");
			OrderList.add(new Order(line));
			LineNumber.put(Integer.parseInt(line[0]), i);

			for(String str : line) {
				try {
					Integer.parseInt(str);
				}catch(NumberFormatException nfe){
					if(str.length() == 1) {
						Var.put(str, 0);
					}
				}
			}
		}

		for(count = 0;count < N && loop && !inf;count++) {
			Order order = OrderList.get(count);
			switch(order.act) {
			case "ADD":
			case "SUB":
				ADDSUBact(order);
				break;
			case "SET":
				SETact(order);
				break;
			case "IF":
				IFact(order);
				break;
			case "HALT":
				loop = false;
				break;
			default:
				break;
			}
		}

		if(inf) {
			System.out.println("inf");
		}else {
			Var.entrySet().stream().sorted((var1,var2)->{
				return var1.getKey().compareTo(var2.getKey());
			}).forEach((entry) -> {
				System.out.println(entry.getKey() + "=" + entry.getValue() );});
		}

		scan.close();
	}

	private void ADDSUBact(Order order) {
		int Num = Var.get(order.var2)
				+ (order.isNumber ? order.con : Var.get(order.var3))
				* (order.act.equals("ADD") ? 1 : -1) ;

		if(Num < 0 || Num >= 16) {
			loop = false;
		}else{
			Var.put(order.var1, Num);
		}
	}

	private void SETact(Order order) {
		if(order.isNumber) {
			Var.put(order.var1, order.con);
		}else {
			Var.put(order.var1, Var.get(order.var2));
		}
	}

	private void IFact(Order order) {
		if(Var.get(order.var1) == 0) {
			return;
		}

		/* 無限ループ判定 */
		if(infLine.containsKey(order.dest) && Var.get(order.var1) == infLine.get(order.dest)) {
			inf = true;
		}else {
			infLine.put(order.dest,Var.get(order.var1));
		}

		if(LineNumber.containsKey(order.dest)) {
			count = LineNumber.get(order.dest) - 1;
		}else{
			loop = false;
		}
	}
}

class Order{
	String act,var1,var2,var3;
	int con,dest,line;
	boolean isNumber = false;

	public Order(String Line[]) {
		line = Integer.parseInt(Line[0]);
		act = Line[1];

		switch(act) {
		case "ADD":
		case "SUB":
			var1 = Line[2];
			var2 = Line[3];
			try {
				con = Integer.parseInt(Line[4]);
				isNumber = true;
			}catch (NumberFormatException nfe){
				var3 = Line[4];
			}
			break;
		case "SET":
			var1 = Line[2];
			try {
				con = Integer.parseInt(Line[3]);
				isNumber = true;
			}catch (NumberFormatException nfe){
				var2 = Line[3];
			}
			break;
		case "IF":
			var1 = Line[2];
			dest = Integer.parseInt(Line[3]);
			break;
		case "HALT":
		default:
			break;
		}
	}
}


Measured memory_bytes: 70852
#include <iostream>
#include <vector>
#define REP(i, n) for(int i = 0; i < (n); i++)

using namespace std;
typedef long long ll;

int main()
{
  ll N, T;
  cin >> N >> T;
  vector<ll> A(N);
  REP(i, N) cin >> A[i];

  vector<ll> maxA(N); // maxA[i] := [i, N)までみたときの最大値
  maxA[N - 1] = A[N - 1];
  for (int i = N - 2; i >= 0; i--) {
    maxA[i] = max(A[i], maxA[i + 1]);
  }

  ll ma = -1;
  REP(i, N - 1) {
    ma = max(ma, T*(maxA[i + 1] - A[i]) / 2);
  }

  ll ans = 0;
  REP(i, N - 1) {
    ll tmp = T*(maxA[i + 1] - A[i]) / 2;
    if (tmp == ma) ans++;
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 1792
import java.util.Scanner;
 
public class Main {
 
    public static void main(String args[]) throws Exception {
 
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        int C = sc.nextInt();
        int X = sc.nextInt();
 
        int res = 0;
        int cnt = 0;
        for (int a = 0; a <= A; a++) {
            for (int b = 0; b <= B; b++) {
                for (int c = 0; c <= C; c++) {
                    res = 500 * a + 100 * b + 50 * c;
                    if (res == X) {
                        cnt++;
                    }
                }
            }
        }
        System.out.println(cnt);
    }
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const long long MOD=998244353;
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)

int main(void){
    int n,k;
    cin>>n>>k;
    vector<int> P(n);
    rep(i,n) cin>>P[i];
    vector<double> sums(n+1);
    sums[0]=0;
    rep(i,n) sums[i+1]=sums[i]+(double)(P[i]+1)/2;
    //rep(i,n+1) cout<<sums[i]<<endl;
    double ans=0;
    rep(i,n-k+1){
        double temp=sums[i+k]-sums[i];
        //cout<<temp<<endl;
        chmax(ans,temp);
    }
    printf("%.15f\n",ans);
    return 0;
}

Measured memory_bytes: 5616
def makebit(n, d):
	lst = []
	m = n
	for i in range(0, d):
		lst.append(m%2==1)
		m = m / 2
	return lst
D, G = map(int, raw_input().split())
plist = []
clist = []
for i in range(0, D):
	p, c = map(int, raw_input().split())
	plist.append(p)
	clist.append(c)
n = 1
for i in range(0, D):
	n = n * 2
lst = []
for i in range(0, n):
	lst.append(makebit(i, D))
min = 10000
for i in range(0, n):
	sum = 0
	cnt = 0
	for j in range(0, D):
		if lst[i][j]:
			sum += (j+1)*100*plist[j] + clist[j]
			cnt += plist[j]
	for j in range(0, D):
		if not lst[i][-1-j]:
			if sum + (D-j)*100*(plist[-1-j]-1) < G:
				sum += (D-j)*100*(plist[-1-j]-1)
				cnt += plist[-1-j] - 1
			elif sum < G:
				for k in range(0, plist[-1-j]-1):
					sum += (D-j)*100
					cnt += 1
					if G <= sum: break
		if G <= sum: break
	if cnt < min and G <= sum:
		min = cnt
print min

Measured memory_bytes: 2820
function Scanner(input) {
	var self = this;
	self.itemNo = 0;
	self.orgStr = input;
	self.splitedStrs = (function(target) {
		var result = [];
		var target = target.replace(/[\n \t]+/g, " ");
		var strs = target.split(" ");
		for (var i = 0, len = strs.length; i < len; i++) {
			result.push(strs[i]);
		}
		return result;
	}(input));

	self.next = function() {
		var result = self.splitedStrs[self.itemNo];
		self.itemNo++;
		return (result != null) ? result : null;
	}

	self.nextInt = function() {
		var result = self.splitedStrs[self.itemNo];
		self.itemNo++;
		return (result != null) ? parseInt(result) : null;
	}

	self.nextBigDecimal = function() {
		var result = self.splitedStrs[self.itemNo];
		self.itemNo++;
		return (result != null) ? parseFloat(result) : null;
	}
	
	self.nextByte = function() {
		var result = self.splitedStrs[self.itemNo];
		self.itemNo++;
		return (result != null) ? new Int8Array(result) : null;
	}

}

function Main(sc) {

	var K = sc.nextInt();
	var S = sc.next();
	
	if (K < S.length) {
		ans = S.substring(0, K) + "...";
	}
	else {
		ans = S;
	}
	
	console.log(ans);
}
Main(new Scanner(require("fs").readFileSync("/dev/stdin", "utf8")));
// Main(new Scanner("10 1 2 5 3 4 6 7 3 2 4 1 2 2 3 3 4 4 5 3 6 6 7 1 8 8 9 9 10"));

// var str1 = sc.next(); // Stringで取得
// var int1 = sc.nextInt(); // intで取得
// var bd1 = sc.nextBigDecimal(); // BigDecimalで取得
// var byte1 = sc.nextByte(); // byteで取得
// for (var i = 0; i < 1000000000; i++) var toDelay = "aaa"; // 1000msくらいの遅延
// console.log(wrtnNos); return;


Measured memory_bytes: 29640
#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
    int n,a[100000]={0},b=0,c=0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n,greater<int>());
    for(int i=0;i<n;i++){
        if(a[i]!=b){
            c++;
            b=a[i];
        }else{
            c--;
            b=0;
        }
    
    }
    cout<<c<<endl;
}


Measured memory_bytes: 640
fun main(args: Array<String>) {
    val s = readLine()!!.split("").drop(1).dropLast(1)

    var min = Integer.MAX_VALUE
    for(i in (0 until s.size - 2)){
        val num = "${s[i]}${s[i+1]}${s[i+2]}".toInt()
        val diff = Math.abs(753 - num)
        if(min > diff) min = diff
    }

    println(min)
}

Measured memory_bytes: 36084
// ABC136B.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

#include <iostream>
using namespace std;
int main()
{
	int N;
	cin >> N;

	int ans = 0;
	if (N<10)
	{
		ans = N;
	}
	else if (N<=99)
	{
		ans = 9;
	}
	else if (N<=999)
	{
		ans = N - 90;
	}
	else if (N<=9999)
	{
		ans = 909;
	}
	else if (N<100000)
	{
		ans = N - 9090;
	}
	else if (N=100000)
	{
		ans = 90909;
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	while(cin>>n){
		vector<int>data(n+1);int res=0;
		for(int i=1;i<=n;i++)cin>>data[i];
		for(int i=1;i<=n;i++){if(data[data[i]]==i)res++;}
		cout<<res/2<<endl;
	}
}

Measured memory_bytes: 640
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N = I()
    a = [I() - 1 for _ in range(N)]

    c = 0
    ans = 0
    is_ok = True
    while True:
        c = a[c]
        ans += 1
        if c == 0 or ans > N:
            is_ok = False
            break
        if c == 1:
            break

    if is_ok:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    resolve()

Measured memory_bytes: 13048
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

//typedef pair<int,int> P;



int main(){
	char s[50][51];
	int H,W;

	scanf("%d %d", &H,&W);

	for(int i=0;i<H;i++){
		scanf("%s", s[i]);
	}

	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			if(s[i][j]=='#'){
				bool ok = false;
				if(i>0 && s[i-1][j]=='#') ok = true;
				if(i<H && s[i+1][j]=='#') ok = true;
				if(j>0 && s[i][j-1]=='#') ok = true;
				if(j<W && s[i][j+1]=='#') ok = true;
				if(!ok){
					printf("No\n");
					return 0;
				}
			}
		}
	}

	printf("Yes\n");

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#include <utility>
#define llint long long
#define inf 1e18
#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)
#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))

using namespace std;
typedef pair<llint, llint> P;

llint D;
llint c[30], csum;
llint s[400][30];
llint ans[405];

llint score(llint ans[], llint n)
{
	llint last[26];
	for(int i = 0; i < 26; i++) last[i] = 0;
	
	llint ret = 0, sub = 0;
	for(int i = 1; i <= n; i++){
		llint x = ans[i];
		ret += s[i][x];
		sub -= (i-last[x]) * c[x];
		sub += csum;
		ret -= sub;
		last[x] = i;
	}
	return ret;
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	srand(time(NULL));
	
	cin >> D;
	for(int i = 0; i < 26; i++) cin >> c[i];
	for(int i = 1; i <= D; i++){
		for(int j = 0; j < 26; j++){
			cin >> s[i][j];
		}
	}
	for(int i = 0; i < 26; i++) csum += c[i];
	
	for(int i = 1; i <= D; i++){
		llint max_val = -inf, max_j;
		for(int j = 0; j < 26; j++){
			ans[i] = j;
			llint res = score(ans, i);
			if(res > max_val){
				max_j = j;
				max_val = res;
			}
		}
		ans[i] = max_j;
	}
	
	llint cur = score(ans, D);
	for(int t = 0; t < 1000000; t++){
		llint x = rand() % D + 1, y = rand() % D + 1;
		swap(ans[x], ans[y]);
		llint nxt = score(ans, D);
		if(nxt < cur) swap(ans[x], ans[y]);
		
		x = rand() % D + 1, y = rand() % 26;
		llint tmp = ans[x];
		ans[x] = y;
		nxt = score(ans, D);
		if(nxt < cur) ans[x] = tmp;
	}
	
	for(int i = 1; i <= D; i++) cout << ans[i]+1 << endl;
	
	
	return 0;
}

Measured memory_bytes: 3756
#include <bits/stdc++.h>
using namespace std;
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; }
int main(void){
    int n; cin>>n;
    vector <int> a(n);
    for(int i=0;i<n;i++){
    cin>>a[i];
    }
    vector <int> dp(n,1e9);
    dp[0]=0;
    dp[1]=abs(a[1]-a[0]);
    
    for(int i=2;i<n;i++){
        chmin(dp[i],dp[i-1]+abs(a[i-1]-a[i]));
        chmin(dp[i],dp[i-2]+abs(a[i-2]-a[i]));
        //cout<<i<<'*'<<dp[i]<<endl;
    }
    
    cout<<dp[n-1]<<endl;
}

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

using namespace std;
#define INF 1000007
#define MOD 1000000007
#define ll long long
#define maxn 100
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, n) FOR(i, 0, n)

typedef std::pair<int, int> P;

vector<bool> prime(maxn + 1, true); //素数テーブル
void prime_table(void) {
    prime[0] = false;
    prime[1] = false;
    for (int i = 2; i * i <= maxn; i++) {
        if (!prime[i]) {
            continue;
        }
        for (int j = i + i; j <= maxn; j += j + i) {
            prime[j] = false;
        }
    }
}

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

int lcm(int a, int b) { return a / gcd(a, b) * b; }

bool IsPrime(int num) //素数判定
{
    if (num < 2)
        return false;
    else if (num == 2)
        return true;
    else if (num % 2 == 0)
        return false;

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2) {
        if (num % i == 0) {
            return false;
        }
    }

    return true;
}

vector<int> divisor(int n) //約数列挙
{
    vector<int> ret;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i - 1);
            if (i * i != n) {
                ret.push_back((n / i) - 1);
            }
        }
    }
    sort(ret.begin(), ret.end());
    return (ret);
}

int a, b;

void f(int x) {
    a = x % 10;
    b = 0;
    while (x) {
        b = x;
        x /= 10;
    }
}

signed main() {
    int N;
    cin >> N;
    string S;
    cin >> S;
    ll r, b, g;
    r = b = g = 0;
    rep(i, N) {
        if (S[i] == 'R')r++;
        if (S[i] == 'G')g++;
        if (S[i] == 'B')b++;
    }
    ll ans = r * b * g;
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            int k = j + j - i;
            if (S[i] == S[j])continue;
            else if (k < N && S[j] != S[k] && S[i] != S[k])ans--;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3624
#include<iostream>
#include<queue>

using namespace std;

typedef pair<int, int > P;
int d[51][51];
int H, W;
char maze[51][51];

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

int bfs(){
    queue<P > que;
    que.push(P(0, 0));
    d[0][0] = 0;
    while(que.size()){
        P p = que.front(); que.pop();  
        if(p.first==H || p.second==W){
            break;
        }
        for (int i=0; i<4; i++){
            int nx = p.first + dx[i];
            int ny = p.second + dy[i];
               // cout << "next:"  << nx << ", " << ny << endl;;
            if(0<=nx && nx<=H-1 && 0<=ny && ny<=W-1 && maze[nx][ny]=='.' && d[nx][ny]==INF){
                que.push(P(nx, ny));
                d[nx][ny] = d[p.first][p.second] + 1;
            }
            
        }
    }
    return d[H-1][W-1];
}
int main(){
    cin >> H >> W;
    int black_num = 0;
    for(int i=0; i<H; i++){
        for(int j=0; j<W; j++){
            cin >> maze[i][j];
            if(maze[i][j]=='#'){
                black_num += 1;
            }
            d[i][j] = INF;
        }
    }
    int length = bfs();
    int ans;
    if (bfs()!=INF){
        ans = H*W;
        ans -= length;
        ans -= black_num;
        ans -= 1;
        cout << ans << endl;
    }else{
        cout << -1 << endl;
    }
    /*
    for(int i=0; i<H; i++){
        for(int j=0; j<W; j++){
            cout << d[i][j] << ", ";
        }
        cout << endl;
    }
    */
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _USE_MATH_DEFINES
using namespace std;
// 型シノニム
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;
// 定数
constexpr ll INF   = 1e16;
constexpr ll INM   = 114514;
constexpr ll MOD   = 1e9 + 7;
constexpr ld EPS   = 1e-12;
constexpr ll dx[4] = {1, 0, -1, 0};
constexpr ll dy[4] = {0, 1, 0, -1};
// 便利関数
void IOS() { ios::sync_with_stdio(false), cin.tie(0); }
template <typename T>
void dump(T x) { cout << x << endl; }
void dumpf(ld x, ll t) { cout << setprecision(t) << fixed << x << endl; }
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
	fill((T *)array, (T *)(array + N), val);
}
inline ll mod(ll a, ll mod) {
	if (a > 0) return a % mod;
	if (a % mod == 0) return 0;
	ll x = -a / mod + 1;
	a += x * mod;
	return a % mod;
}
ll powm(ll a, ll b, ll m) {
	if (b == 0) {
		return 1;
	} else if (b % 2 == 0) {
		ll d = powm(a, b / 2, m);
		return (d * d) % m;
	} else {
		return (powm(a, b - 1, m) * a) % m;
	}
}
// 本体

ll a[(ll)1e6 + 3] = {}; // 元の金or返ってくる金の小さいほう
ll b[(ll)1e6 + 3] = {};
int main() {
	IOS();
	ll n, m;
	cin >> n >> m;
	vector<ll> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	ll l = a[0] / 2;
	for (int i = 1; i < n;i++) {
		l = lcm(l, a[i] / 2);
	}
	bool ok = true;
	for (int i = 0; i < n;i++) {
		ll div = l / (a[i] / 2);
		if(div % 2 == 0) {
			ok = false;
		}
	}
	if(!ok) {
		dump(0);
		return 0;
	}
	dump(m / l - m / (l * 2));
}

Measured memory_bytes: 3968
inf=float('inf')
n, m=map(int, input().split())
abc=[list(map(int, input().split())) for i in range(m)]
abc=[[ai[0]-1, ai[1]-1, -ai[2]] for ai in abc]
d=[inf]*n
d[0]=0
for i in range(n):
    flag=False
    for abci in abc:
        if d[abci[1]]>d[abci[0]]+abci[2]:
            flag=True
            d[abci[1]]=d[abci[0]]+abci[2]
            if i==n-1 and abci[1]==n-1:
                print('inf')
                exit()

print(-d[n-1])

Measured memory_bytes: 3828
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int acs(const void *a, const void *b) { 
  return *(int*)a - *(int*)b;
} /* 1,2,3,4.. */
int des(const void *a, const void *b) {
  return *(int*)b - *(int*)a;
} /* 8,7,6,5.. */
int cmp_char(const void *a, const void *b) { 
  return *(char*)a - *(char*)b;
} /* a,b,c,d.. */
int cmp_str(const void *a, const void *b) {
  return strcmp(*(const char **)a, *(const char **)b);
} /* aaa,aab.. */
#define min(a,b) (a < b ? a : b)
#define max(a,b) (a > b ? a : b)
#define rep(i, l, r) for (int i = l; i < r; i++)
#define MAX 100001
#define MOD 1000000007
#define INF 1000000009
typedef long long int lli;

int main(void) {
  int A[3][3];
  int n, b[11];
  rep(i, 0, 3) rep(j, 0, 3) scanf("%d", &A[i][j]);
  scanf("%d", &n);
  rep(i, 0, n) scanf("%d", &b[i]);

  int a[3][3] = {0};
  rep(ni, 0, n) {
    rep(i, 0, 3) {
      rep(j, 0, 3) {
        if (A[i][j] == b[ni]) a[i][j] = 1;
      }
    }
  }
  //　横
  rep(i, 0, 3) {
    int ok = 1;
    rep(j, 0, 3) {
      if (a[i][j]) continue;
      ok = 0;
      break;
    }
    if (ok) {
      printf("Yes\n");
      return 0;
    }
  }
  //　横
  rep(j, 0, 3) {
    int ok = 1;
    rep(i, 0, 3) {
      if (a[i][j]) continue;
      ok = 0;
      break;
    }
    if (ok) {
      printf("Yes\n");
      return 0;
    }
  }
  //　横
  if (a[0][0] && a[1][1] && a[2][2]) {
    printf("Yes\n");
    return 0;
  }
  if (a[0][2] && a[1][1] && a[2][0]) {
    printf("Yes\n");
    return 0;
  }
  printf("No\n");
  return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
#include<cmath>
#include<climits>
#include<queue>
#include<stack>
#include<numeric>
#include<set>
#include<iomanip>
#include<map>
using namespace std;


typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)


int main(){
  int n, h;
  cin >> n >> h;
  vector<pair<int, int> > s(n), r(n);
  rep(i, n){
    int a, b;
    cin >> a >> b;
    s[i].first = a;
    s[i].second = b;
    r[i].first = b;
    r[i].second = a;
  }

  sort(s.begin(), s.end());
  sort(r.begin(), r.end());

  reverse(s.begin(), s.end());
  reverse(r.begin(), r.end());


  int itr = 0;
  int ans = 0;
  while(h > 0){
    if(s[0].first > r[itr].first){
      ans += h / s[0].first;
      if(h % s[0].first != 0) ans++;
      break;
    } else {
      h -= r[itr].first;
      itr++;
    }
    ans++;
  }

  cout << ans << endl;


}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;

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

void max_heapify(vll &a, int h, int i1) {
  int i = i1 - 1,
      l = i1 * 2 - 1,
      r = i1 * 2;
  int largest = i;
  
  if (l <= h && a[l] > a[i]) largest = l;
  if (r <= h && a[r] > a[largest]) largest = r;

  if (largest != i) {
    swap(a[i], a[largest]);
    max_heapify(a, h, largest + 1);
  }
}

void build_max_heap(vll &a, int h) {
  for (int i = h / 2; i >= 1; i--) max_heapify(a, h, i);
}

int main() {
  int h;
  cin >> h;
  
  vll heap(h);
  rep(i, h) cin >> heap[i];
  
  build_max_heap(heap, h);

  rep(i, h) printf(" %lld", heap[i]);
  cout << endl;
}



Measured memory_bytes: 6704
#include<bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
long long int m=1000000007;
long long int power(long long int p,long long int k)
{
long long int a=1;
while(k)
{
if(k&1)
a=(a*p)%m;
p=(p*p)%m;
k>>=1;
}
return a;
}
int main()
{
ll n;
cin>>n;
ll a[n],i;
for(i=0;i<n;i++)
cin>>a[i];
ll ans=0,k=0;
for(i=0;i<n;i++)
{
if(a[i]>=a[i+1])
k++;
else
{
ans=max(k,ans);
k=0;
}
}
if(ans>=1)
cout<<ans;
else
cout<<"0";
return 0;
}

Measured memory_bytes: 1024
import * as fs from 'fs';

const input = fs.readFileSync('/dev/stdin', 'utf8');

_c(input);

// 盤面はそこまで大きくない
// 列や行を入れ替えても計算に支障はない（合計なので、順番は関係ない）
// K を下回った場合はそれ以上増やしても意味がない
// よくわからん！指数オーダーだけど全部試そう！

function _c(input: string) {
  const [_HWK, ...C] = input.split('\n');
  const [H, W, K] = _HWK.split(' ').map((s) => parseInt(s));
  const Black = [] as (1 | 0)[][];
  let sum = 0;
  for (let y = 0; y < H; y++) {
    const line = C[y];
    Black[y] = [];
    for (let x = 0; x < line.length; x++) {
      const color = line[x];
      if (color === '#') {
        Black[y].push(1);
        sum++;
      } else {
        Black[y].push(0);
      }
    }
  }
  // console.log(Black, sum);

  const target = sum - K; // 消したい数

  // 全パターンマスクして、消した数を数える
  let patterns = 0;
  for (let maskY = 0; maskY < 2 ** H; maskY++) {
    for (let maskX = 0; maskX < 2 ** W; maskX++) {
      calculate: {
        let masked = 0;
        for (let y = 0; y < Black.length; y++) {
          const line = Black[y];
          const isMaskedY = ((maskY >> y) & 1) === 1;
          for (let x = 0; x < line.length; x++) {
            if (line[x] === 1) {
              // 行または列がマスクされているならば、インクリメント
              if (isMaskedY || ((maskX >> x) & 1) === 1) {
                masked++;

                // 超えてしまったら望みはない
                if (masked > target) {
                  break calculate;
                }
              }
            }
          }
        }
        if (masked === target) {
          patterns++;
        }
      }
    }
  }

  console.log(patterns);
}


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

int maxv;
string str;

bool match(char l, char r){
  if ( l == '[' ) return r == ']';
  if ( l == ']' ) return r == '[';
  if ( l == '(' ) return r == ')';
  if ( l == ')' ) return r == '(';
  if ( l == '{' ) return r == '}';
  if ( l == '}' ) return r == '{';
  assert(false);
}

bool isParin(string s){
  if ( s.size()%2==0 || s.size() < 3) return false;
  int c = s.size()/2;
  if ( !(s[c-1] == 'i' && s[c] == 'w' && s[c+1] == 'i') ) return false;

  for ( int i = 0; i < s.size()/2-1; i++ ){
    char left = s[i];
    char right = s[s.size()-i-1];
    if ( !match(left, right) ) return false;
  }
  return true;
}

void rec(int pos, string cur){
  if ( pos == str.size() ){
    if ( isParin(cur) ){
      maxv = max(maxv, (int)cur.size());
    }
    return;
  }

  rec(pos+1, cur + str[pos]);
  rec(pos+1, cur);

}

main(){
  cin >> str;
  maxv = 0;
  rec(0, "");
  cout << maxv << endl;

}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pll;
const int N=1e6;
ll v[N+10];

int main()
{
  ll n,x,y;

 cin>>n>>x>>y;

  ll sum=n/x;

 if(n%x==0)
 {
     cout<<sum*y<<endl;
 }
 else
 {
     sum++;
     cout<<sum*y<<endl;
 }
}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
//#include <atcoder/all>
//using namespace atcoder;
template <typename T> bool chmax(T &u, const T z) { if (u < z) {u = z; return true;} else return false; }
template <typename T> bool chmin(T &u, const T z) { if (u > z) {u = z; return true;} else return false; }
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
typedef pair<ll, ll> P;
const ll INF = 1LL << 60;
//const int MOD = 1000000007;
const ll MOD=998244353;
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }

int main(){
  ll n,x,m;
  cin>>n>>x>>m;
  vector<ll>a(101010),b;
  vector<ll> used(101010,0);
  ll sum=x;
  a[1]=x;
  used[x]=1;
  b.push_back(x);
  int start=0;
  bool hantei=false;
  for(int i=2;i<=n;i++){
    a[i]=((a[i-1]%m)*a[i-1])%m;
    //cout<<a[i]<<" ";
    sum+=a[i];
    if(used[a[i]]>0){
      start=a[i];
      hantei=true;
      break;
    }
    b.push_back(a[i]);
    used[a[i]]++;
  }
  if(hantei==false){
    cout<<sum<<endl;
    return 0;
  }
  ll wa1=0;
  int kazu=0;
  rep(i,b.size()){
    if(b[i]!=start)wa1+=b[i];
    else {
      kazu=i;
      break;
    }
  }
  ll wa2=0;
  for(int i=kazu;i<b.size();i++){
    wa2+=b[i];
  }
  ll ans=wa1+(n-kazu)/(b.size()-kazu)*wa2;
  int amari=(n-kazu)%(b.size()-kazu);
  if(amari!=0){
    for(int i=kazu;i<amari+kazu;i++){
      ans+=b[i];
    }
  }
  cout<<ans<<endl;
  return 0;
}

  

Measured memory_bytes: 5416
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <chrono>

using namespace std;

int main(int argc, const char * argv[]) {
     
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    vector<bool> is_prime(100001, true);
    is_prime[0] = false; is_prime[1] = false;
    for (int i = 2; i <= 100000; i++) {
        if (is_prime[i]) {
            for (int j = 2 * i; j <= 100000; j += i) {
                is_prime[j] = false;
            }
        }
    }
    
    vector<int> cumsum(100001, 0);
    for (int i = 3; i <= 100000; i++) {
        if (is_prime[i] && is_prime[(i + 1) / 2]) {
            cumsum[i] = cumsum[i - 1] + 1;
        } else cumsum[i] = cumsum[i - 1];
    }
    
    int q; cin >> q;
    for (int i = 0; i < q; i++) {
        int l, r; cin >> l >> r;
        cout << cumsum[r] - cumsum[l - 1] << endl;
    }
    
    return 0;
}


Measured memory_bytes: 1024
#include<iostream>
using namespace std;
int a[]={25,10,5,1};
int n;
main()
{
	cin>>n;
	int ans=0;
	for(int i=0;i<4;i++)
	{
		ans+=n/a[i];
		n%=a[i];
	}
	cout<<ans<<endl;
}



Measured memory_bytes: 3104
#include <cstring>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

#include <queue>
#include <cstdio>
inline int getInt(){ int s; scanf("%d", &s); return s; }

#include <set>

using namespace std;

vector<vector<pair<int, int> > > g;
int n;
int c[1000];

int solve(int pos, int prev){
  int ret = 0;
  REP(i,g[pos].size()){
    const int next = g[pos][i].first;
    const int cost = g[pos][i].second;
    if(next == prev) continue;
    if(c[next] == 0) ret += min(cost, solve(next, pos));
    else ret += cost;
  }
  return ret;
}

int main(){
  n = getInt();
  g = vector<vector<pair<int, int> > >(n);
  REP(i,n-1) c[i + 1] = getInt();
  REP(i,n-1){
    const int u = getInt();
    const int v = getInt();
    const int p = getInt();
    g[u].push_back(make_pair(v, p));
    g[v].push_back(make_pair(u, p));
  }
  printf("%d\n", solve(0, -1));
  return 0;
}

Measured memory_bytes: 1100
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,int> pli;
typedef pair<int,int> pii;
#define rep(i,a,b) for(ll i=a ; i<b ; i++)
#define qrep(que, ite) for(auto ite=begin(que) ; ite!=end(que) ; ite++)
const int max_n = 1e5;
const ll mod = 1e9+7;
const ll INF = 1e17;
const int inf = 1e5;
//typedef long double ld;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll a, ll b) { return a ? gcd(b%a, a) : b; }
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
ll mo = 998244353;
struct UnionFind {
    vector<int> par;

    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }

    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }

    bool issame(int x, int y) {
        return root(x) == root(y);
    }

    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    int size(int x) {
        return -par[root(x)];
    }
};
struct SegmentTree{
  int N;
  vector<int> node;
  public :
    void intit(vector<int>v){
      int sz = v.size();
      N=1;
      while(N<sz) N*=2;
      node.resize(N);
      for(int i=0 ; i<sz ; i++) node[i+N-1] = v[i];
      for(int i=N-2 ; i>=0 ; i--) node[i] = min(node[i*2+1], node[i*2+2]);
    }
    void update(int x, int val){
      x += N-1;
      node[x+N-1] = val;
      while(x>0){
        x = (x-1)/2;
        node[x] = min(node[x*2+1], node[x*2+2]);
      }
    }
    int getmin(int a, int b, int k, int l, int r){
      if(b<=l || r<=a) return inf;
      else if(a<=l && r<=b) return node[k];
      else{
        int vl = getmin(a, b, 2*k+1, l, (l+r)/2);
        int vr = getmin(a, b, 2*k+2, (l+r)/2, r);
        return min(vl, vr);
      }
    }
};
struct func{
  int num, denom;
  func(int num, int denom=1)
    : num(num), denom(denom)
    {

    }
  ~func(){

  }
};
func operator +(func const &l, func const &r){
  if(l.denom==r.denom) return func(l.num+r.num, l.denom);
  return func(l.num*r.denom+r.num*l.denom, l.denom*r.denom);
}
struct IntLike{
  int data;
  IntLike(int data)
    : data(data)
    {}
  IntLike operator +(IntLike const & right){
    return IntLike{data + right.data};
  }
};
struct array3{
  int storage[3];
  int & operator [](size_t i){
    return storage[i];
  }
};
int main(){
  string s; cin>>s;
  ll K; cin>>K;
  rep(i,0,s.size()){
    int now = s[i]-'a' + 1;
    if(K<=0) break;
    if(now+K-1>=26 && s[i]!='a'){
      s[i] = 'a';
      K -= 26-now+1;
    }
  }
  if(K>0){
    K %=26;
    for(char c='a' ; c<='z' ; c++){
      if((-(s.back()-'a')+c-'a')%26==K){
        s.back() = c;
        break;
      }
    }
  }
  cout<<s<<endl;
  return 0;
}


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

int main() {
  int A, B, C;
  cin >> A >> B >> C;
  
  if (A < C && C < B){
    cout << "Yes" << endl;
  } else if (B < C && C < A){
    cout << "Yes" << endl;
  } else {    
    cout << "No" << endl;
  }
}

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

using namespace std;

const int N = 100000 + 7;

typedef pair<int, int> ii;

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


Measured memory_bytes: 256
#include "bits/stdc++.h"
#ifndef err
#define err(...)(void)0
#endif
using namespace std;
using ll = long long;
using ull = decltype(1ull);
template<class T>int size(T&&a) { return a.size(); }
#define REP(t,a)for(typename make_signed<decltype(a.second)>::type t=a.first,_l##t=a.second;t<_l##t;t++)
#define RREP(t,a)for(typename make_signed<decltype(a.second)>::type t=a.second-1,_l##t=a.first;t>=_l##t;t--)
template<class B>pair<int, B>make_pair(B b) { return{ 0,b }; }
#define rep(t,...)REP(t,make_pair(__VA_ARGS__))
#define rrep(t,...)RREP(t,make_pair(__VA_ARGS__))
#define all(a)begin(a),end(a)
#define rall(a)a.rbegin(),a.rend()
#define var(t, ...) t __VA_ARGS__;in,__VA_ARGS__;

void Calc();
int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
  cin.exceptions(istream::failbit | istream::badbit);
  cout << fixed << setprecision(15); Calc(); cout.flush(); return 0;
}
template<class A>void amax(A&a, A b) { a = max(a, b); }
template<class A>void amin(A&a, A b) { a = min(a, b); }
template<class A>int comp(A a, A b) { return a < b ? 1 : b < a ? -1 : 0; }
struct Scanner {
  template<class A = string>A Next() { A a; cin >> a; return a; }
  template<class A = int>vector<A>Array(int n) { vector<A>a(n); for (A&i : a) cin >> i; return a; }
  string Line() const { string s; getline(cin, s); return s; }
  template<class A>Scanner&operator,(A&a) { a = Next<A>(); return *this; }
  template<class A>operator A() { return Next<A>(); }
}in;

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


ll solve(int n, ll sum, std::vector<int, std::allocator<int>> &a) {
  ll ans = 0;
  bool is = sum > 0;

  rep(i, 1, n) {
    sum += a[i];
    if (is) {
      if (sum >= 0) {
        ans += sum + 1;
        sum = -1;
      }
    }
    else {
      if (sum <= 0) {
        ans += -sum + 1;
        sum = 1;
      }
    }
    is = !is;
    err(sum, ans);
  }
  return ans;
}

void Calc() {
  int n = in;
  auto a = in.Array(n);

  ll ans = 0;
  if (a[0] == 0) {
    ans = solve(n, -1, a) + 1;
    amin(ans, solve(n, 1, a) + 1);
  }
  else {
    ll sum = a[0];

    ans = solve(n, sum, a);
    if (a[0] > 0) {
      amin(ans, solve(n, -1, a) + a[0] + 1);
    }
    else {
      amin(ans, solve(n, 1, a) - a[0] + 1);
    }
  }
  cout << (ans) << endl;

}


Measured memory_bytes: 640
n = int(input())
rows = []
for i in range(2):
    rows.append(list(map(int, input().split())))

max_candies = 0
for j in range(n):
    if sum(rows[0][:j+1]) + sum(rows[1][j:]) > max_candies:
        max_candies = sum(rows[0][:j+1]) + sum(rows[1][j:])

print(max_candies)

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

// しゃくとりで解きなおす

int main() {
  long long n, m, k;
  cin >> n >> m >> k;
  vector<long long> a(n+1), b(m+1);
  int ans = 0, ar, br = 0;
  for(int i = 1; i <= n; i++){
    cin >> a.at(i);
    a.at(i) += a.at(i-1);
    if(a.at(i) <= k) ar = i;
  }
  for(int i = 1; i <= m; i++){
    cin >> b.at(i);
    b.at(i) += b.at(i-1);
  }
  
  for(int i = ar; i >= 0; i--){
    for(int j = br; j <= m; j++){
      if(a.at(i) + b.at(j) <= k){
        br = j;
        ans = max(ans, i + br);
      }
      else break;
    }
    if(br == m) break;
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 6388
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<pair<int, int> > vpii;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef vector<ll> vll;
#define INF 0x3f3f3f3f
#define MOD 998244353LL
#define EPS 0.00001
#define f first
#define s second
#define pb push_back
#define mp make_pair

#define FOR(i, a, b) for (int i=(a); i<=(signed)(b); i++)
#define F0R(i, a) for (int i=0; i<(signed)(a); i++)
#define RFOR(i, a, b) for (int i=(a); i >= b; i--)

#define MN 200005
int n, k;
int a[MN];
int b[MN];

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

    cin >> n >> k;
    FOR(i, 1, n) cin >> a[i];
    F0R(_, k){
        FOR(i, 1, n){
            b[max(1, i-a[i])]++;
            b[min(n+1, i+a[i]+1)]--;
        }
        FOR(i, 1, n) b[i] += b[i-1];
        bool ch = false;
        FOR(i, 1, n){
            a[i] = b[i];
            b[i] = 0;
            if(a[i] != n) ch = true;
        }
        if(!ch) break;
    }
    FOR(i, 1, n) cout << a[i] << " ";
    cout << "\n";

    return 0;
}


Measured memory_bytes: 5216
#include<bits/stdc++.h>
using namespace std;
#define crap ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
typedef long long int ll;
typedef unsigned long long ull;
typedef std::vector<int> vi;
typedef std::vector<ll> vll;
typedef std::vector<vi > vvi;
typedef std::vector<vll > vvll;
typedef std::pair<int,int> ii;
typedef std::pair< ll, ll > lp;
typedef std::vector<ii> vii;
typedef std::vector<vii > vvii;

#define pb push_back 
#define PB pop_back
#define pf push_front
#define PF pop_front
#define mp make_pair
#define ub(a,b) upper_bound(all(a),b)
#define lb(a,b) lower_bound(all(a),b)
#define bs(a,b) binary_search(all(a),b)
#define mem(a,b) memset(a,b,sizeof(a))
#define in(a,n) F(i,0,n-1)cin>>a[i]
#define in1(a,n) F(i,1,n)cin>>a[i]
#define out(a,n) F(i,0,n-1)cout<<a[i]<<"";cout<<endl
#define ff first
#define ss second
#define F(i,a,b) for (ll i=a;i<=b;i++)
#define RF(i,a,b) for(ll i=a;i>=b;i--)
#define rep(i,n) F(i,0,n-1)
#define clr(a) (a).clear()
#define rz resize
#define sqr(a) ((a) * (a))
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin() ,(a).rend()
// #define endl '\n'

#define mod 1000000007

ll add(ll a, ll b){return (a%mod + b%mod)%mod;}
ll sub(ll a , ll b){return (a%mod - b%mod + mod)%mod;}
ll mul(ll a, ll b){return (a%mod * b%mod)%mod;}
ll poww(ll a,ll b){ll res=1;while(b){if(b&1){res*=a;}a=a*a;b>>=1;}return res;}
ll poww(ll a,ll b,ll MOD){ll res=1;while(b){if(b&1){res*=a;res%=MOD;}a=a*a;a%=MOD;b>>=1;}return res;}

#define dbg(x) cout<<#x<<" :: "<<x<<endl;
#define dbg2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<endl;
#define dbg4(x,y,z,w) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<"\t"<<#w<<" :: "<<w<<endl;

#define upb upper_bound
#define lwb lower_bound

const int N = 1e5 + 5;

int p[N], r[N];

int find_(int i){
	return (p[i] == i) ? i : p[i] = find_(p[i]);
}

void uni(int u, int v){
	u = find_(u);
	v = find_(v);
	if (u == v)return;

	if (r[u] < r[v])
		swap(u, v);

	p[v] = u;
	r[u] += r[v];
	return; 
}

void pre(){
	rep(i, N)
	{
		p[i] = i;
		r[i] = 1;
	}
}

int main(int argc, char const *argv[])
{
	crap;
	pre();
	int n, m, u, v, z;
	cin >> n >> m ;
	rep(i, m){
		cin >> u >> v >> z;
		uni(u, v);
	}
	set<int> ans;
	F(i, 1 ,n){
		ans.insert(find_(i));
	}

	cout << sz(ans) << endl;
	return 0;
}

Measured memory_bytes: 5760
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define ll long long
#define abs(a) (a>0?a:(-(a)))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
struct node{
	ll x,y,z;
	bool operator <(const node &a)const{
		return x<a.x;
	}
};
priority_queue<node>q;
int main(){
	int n,m;
	ll ans=0;
	scanf("%d%d",&n,&m);
	for (int i=1,x;i<=n;i++)
	scanf("%d",&x),q.push((node){x-x/2,x,2ll}),ans+=x;
	while (m&&!q.empty()){
		node x=q.top();q.pop();
	//	printf("%lld %lld %lld\n",x.x,x.z,ans);
		ans-=x.x;
		m--;
		if ((x.y-x.y/(x.z*2))-(x.y-x.y/(x.z))>0)q.push((node){(x.y-x.y/(x.z*2))-(x.y-x.y/(x.z)),x.y,x.z*2ll});
	}
	printf("%lld\n",ans);
	return 0;
}
/*
x.x 便宜的钱数

x.y/(x.z*2) 该付的钱 
这一轮 这件物品便宜了 x.x 
下一轮 x.y-x.y/(x.z*2) 便宜的钱 
所以下一轮增加的便宜数是  x.y-x.y/(x.z*2)-x.x */

Measured memory_bytes: 4724