akhauriyash/Code-Regression huggingface dataset:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop,heappush

n,m = map(int,readline().split())
a = list(map(int,readline().split()))
xy = list(map(int,read().split()))

if(n-m==1):
    print(0)
    exit()

p = ((n-1)-m)*2
if( p > n):
    print('Impossible')
    exit()

sys.setrecursionlimit(10**9)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self,x):
        if(self.parents[x] < 0):
            return x
        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def size(self, x):
        return self.parents[ self.find(x) ] * -1

    def same(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        return (x_root == y_root)

    def union(self,x,y):
        x_root = self.find(x)
        y_root = self.find(y)
        if(x_root == y_root):
            return

        if( self.parents[x_root] <= self.parents[y_root] ):
            self.parents[x_root] += self.parents[y_root]
            self.parents[y_root] = x_root
        else:
            self.parents[y_root] += self.parents[x_root]
            self.parents[x_root] = y_root

    def members(self,x):
        root = self.find(x)
        ret = [ i for i in range(self.n) if self.find(i) == root ]
        return ret

    def roots(self):
        ret = [ i for i in range(self.n) if self.parents[i] < 0]
        return ret

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

uf = UnionFind(n)
hqs = [[] for _ in range(n)]

it = iter(xy)
for x,y in zip(it,it):
    uf.union(x,y)

for i in range(n):
    root = uf.find(i)
    heappush(hqs[root], a[i])

ans = []
others = []
for i in range(n):
    if(hqs[i]):
        ans.append(heappop(hqs[i]))
        # others += hqs[i]
        others.extend(hqs[i])

others.sort()
rem = p - len(ans)
# ans += others[:rem]
ans.extend(others[:rem])

print(sum(ans))

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


public class Main{

     public static void main(String []args){
        Scanner scanner = new Scanner(System.in);
        String s= scanner.next();
        int n=Integer.valueOf(s);
        
        if(n==1)
        System.out.println(0);
        else if(n==0)
         System.out.println(1);
        
        
        
        //for(int i=0;i<n;i++)
        //int n= scanner.nextInt();
        //System.out.println()
     }
}

Measured memory_bytes: 35556
namespace Coder {
  class Scanner {
    private buffer: string = '';
    private stdinQueue: any = [];

    constructor() {
      process.stdin.resume();
      process.stdin.setEncoding('utf8');
      process.stdin.on(
        'data',
        (chunk): void => {
          this.buffer += chunk;
          while (this.stdinQueue.length > 0) {
            const i = this.buffer.indexOf('\n');
            if (i < 0) {
              break;
            }
            let line = this.buffer.substr(0, i);
            if (line.endsWith('\r')) {
              line = line.slice(0, -1);
            }
            this.buffer = this.buffer.substr(i + 1);
            this.stdinQueue.shift()(line);
          }
        },
      );
    }
    public getLine(): Promise<string> {
      return new Promise((resolve, reject) => {
        const i = this.buffer.indexOf('\n');
        if (i >= 0 && this.stdinQueue.length === 0) {
          let line = this.buffer.substr(0, i);
          if (line.endsWith('\r')) {
            line = line.slice(0, -1);
          }
          this.buffer = this.buffer.substr(i + 1);
          resolve(line);
        } else {
          this.stdinQueue.push(resolve);
        }
      });
    }

    public close(): void {
      process.stdin.pause();
    }
  }

  async function slove() {
    const sc = new Scanner();
    const S = await sc.getLine();
    console.log(S.replace('2017/', '2018/'));
    sc.close();
  }

  slove();
}


Measured memory_bytes: 7500
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <climits>
#include <iomanip>
#include <bitset>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <list>
#include <map>

using namespace std;

int main() {
  int a, b;
  cin >> a >> b;
  cout << (1ll * (a) * (a - 1) / 2) + (1ll * b * (b - 1) / 2) << endl;
  return 0;
}


Measured memory_bytes: 256
/*
AuThOr GaRyMr
技巧:
1.区别对待大数据&小数据！
2.Dp难推时算贡献！
3.long long (尤其乘法)！
4.long long INF 要大
5.Dp on trees: 换根法，每次清空当前的节点和换到的子节点
6.long double | 输出浮点数
7.注意特判!(prince and princess)
8.是否可以记录两个值之间的关系 CSPday2 meal
9.括号-》数组or栈
10.是否可以先构造
11.网络流奇偶构图
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define niv vector<int>
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define KEEP while(1)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
typedef pair<mp,mp> superpair;
int main(){
	int n;
	string s,t;
	cin>>n>>s>>t;
	rep(i,n){
		cout<<s[i]<<t[i];
	}
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int parent(int i) {return i/2;}
int left(int i) {return i*2;}
int right(int i) {return i*2+1;}
int main(){
  int h,tree[100001];
  scanf("%d",&h);
  for(int i=1;i<=h;i++) scanf("%d",&tree[i]);
  for(int i=1;i<=h;i++){
    printf("node %d: key = %d, ",i,tree[i]);
    if(parent(i)>=1) printf("parent key = %d, ",tree[parent(i)]);
    if(left(i)<=h) printf("left key = %d, ",tree[left(i)]);
    if(right(i)<=h) printf("right key = %d, ",tree[right(i)]);
    printf("\n");
  }
  return 0;
}

    



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

template <typename InputIterator>
typename InputIterator::value_type summation(InputIterator first,
                                             InputIterator last) {
  return std::accumulate(first, last, typename InputIterator::value_type());
}
template <typename T>
std::istream &operator>>(std::istream &stream, std::vector<T> &v);
template <typename T1, typename T2>
std::istream &operator>>(std::istream &stream, std::pair<T1, T2> &p);
template <typename T>
std::istream &operator>>(std::istream &stream, std::vector<T> &v) {
  for (auto &i : v) {
    stream >> i;
  }
  return stream;
}
template <typename T1, typename T2>
std::istream &operator>>(std::istream &stream, std::pair<T1, T2> &p) {
  stream >> p.first >> p.second;
  return stream;
}

int main() {
  int64_t x;
  std::cin >> x;

  for (int64_t a = -120; a <= 120; a++) {
    for (int64_t b = -120; b <= 120; b++) {
      if (a * a * a * a * a - b * b * b * b * b == x) {
        std::cout << a << " " << b << std::endl;
        return 0;
      }
    }
  }

  return 0;
}

Measured memory_bytes: 3628
# include <iostream>
# include <algorithm>
#include <array>
# include <cassert>
#include <cctype>
#include <climits>
#include <numeric>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <tuple>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
# include <chrono>
# include <random>
# include <limits.h>
# include <unordered_map>
# include <unordered_set>
# include <deque>
# include <cstdio>
# include <cstring>
#include <stdio.h>
#include <stdlib.h>
#include <cstdint>
#include <cfenv>
//#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
long long MOD = 1000000000 + 7;
constexpr long long INF = std::numeric_limits<LL>::max();
const double PI = acos(-1);
#define fir first
#define sec second
#define thi third
#define debug(x) cerr<<#x<<": "<<x<<'\n'
typedef pair<LL, LL> Pll;
typedef pair<LL, pair<LL, LL>> Ppll;
typedef pair<LL, pair<LL, bitset<100001>>> Pbll;
typedef pair<LL, pair<LL, vector<LL>>> Pvll;
typedef pair<LL, LL> Vec2;
struct Tll { LL first, second, third; };
typedef pair<LL, Tll> Ptll;
#define rep(i,rept) for(LL i=0;i<rept;i++)
#define Mfor(i,mf) for(LL i=mf-1;i>=0;i--)
LL h, w, n, m, k, t, s, q, last, cnt, sum[1000000], ans, dp[1000000][2], a[2000000], b[2000000];
string str, ss, dd;
bool f, ff;
char c;
int di[4][2] = { { 0,1 },{ 1,0 },{ -1,0 } ,{ 0,-1 } };
struct Edge { LL to, cost; };
vector<Edge>vec[10000];
vector<LL>v;
map<string, LL>ma;
set<LL>st;
void YN(bool f) {
	if (f)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}
void yn(bool f) {
	if (f)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}
int main() {
	cin >> n;
	ans = INF;
	for(int i=1;i<n;i++) {
		LL num = 0,ii=i;
		while (ii>0) {
			num+=ii % 10;
			ii /= 10;
		}
		ii = n - i;
		while (ii>0) {
			num += ii % 10;
			ii /= 10;
		}
		ans = min(ans, num);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2560
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<cctype>
#include<string.h>
#include <stdlib.h>

#define PI 3.1415926

int main() {
	int n, x, y;
	int a = 0, b = 0;
	for (int i = 1; i <= 5; i++) {
		scanf("%d", &n);
		if (n == 0) {
			break;
		}
		for (int j = 1; j <= n; j++) {
			scanf("%d %d", &x, &y);
			if (x == y) {
				a += x;
				b += y;
			}
			else if (x < y) {
				b += x + y;
			}
			else {
				a += x + y;
			}
		}
		printf("%d %d\n", a, b);
		a = 0;
		b = 0;
	}
	return 0;
}

Measured memory_bytes: 2660
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
  int n,ans=0;
  cin >> n;
  vector<int> diff(n);
  vector<int> v(n);
  vector<int> c(n);
  int i;
  for(i=0;i<n;i++){
    cin >> v.at(i);
  }
  for(i=0;i<n;i++){
    cin >> c.at(i);
  }
  for(i=0;i<n;i++){
    diff.at(i)=v.at(i)-c.at(i);
  }
  sort(diff.begin(),diff.end());
  reverse(diff.begin(),diff.end());
  for(i=0;i<n;i++){
    if(diff.at(i)<0) break;
    ans+=diff.at(i);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
import java.io.IOException;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {

		//Todo 回文のメソッド作成
		Scanner scan = new Scanner(System.in);
		String s;
		s = scan.next();

		if (s.charAt(2) != s.charAt(3)) {
			System.out.println("No");
			return;
		}

		if (s.charAt(4) != s.charAt(5)) {
			System.out.println("No");
			return;
		}

		System.out.println("Yes");
	}

	/**
	 * 文字列を反転して返す
	 * @param pStr 文字列
	 * @return 反転した文字列
	 */
	public static String myReverse(String pStr) {
		if (pStr.length() < 1) {
			return "";
		}

		StringBuffer sb = new StringBuffer(pStr);
		return sb.reverse().toString();
	}

	/**
	 * 余りを求める。
	 * @param a
	 * @param b
	 * @return 余り。余りがマイナスの時はプラスで返す。
	 */
	public static long myMod(long a, long b) {
		long ret = 0;

		ret = a % b;

		if (ret < 0) {
			ret += b;
		}

		return ret;
	}

	/**
	 * 乗数を求める ※mod対応
	 * @param kisu 基数
	 * @param josu 乗数
	 * @param primeNumMod_0 法 mod値 使わない場合は「0」
	 * @return
	 */
	public static long myPowWithMod(long kisu, long josu, long primeNumMod_0) {

		long ans = 1;

		//乗数が0の場合→1
		if (josu == 0)
			return 1;

		if (primeNumMod_0 == 0) {
			//modを使わないとき

			while (josu > 0) {

				if (josu % 2 == 0) {
					//累乗が偶数の時

					kisu *= kisu;
					josu = josu / 2;
				} else {
					//累乗が奇数の時
					ans *= kisu;
					josu--;
				}
			}

			return ans;

		} else {
			//modを使うとき

			//初めに桁を落とす
			kisu = myMod(kisu, primeNumMod_0);

			while (josu > 0) {

				if (josu % 2 == 0) {
					//累乗が偶数の時

					kisu *= myMod(kisu, primeNumMod_0);
					josu = josu / 2;

				} else {
					//累乗が奇数の時
					ans *= myMod(kisu, primeNumMod_0);
					josu--;

				}
			}

			return myMod(ans, primeNumMod_0);

		}

	}

}


Measured memory_bytes: 22100
#[allow(unused_imports)]
use proconio::{fastout, input};

#[fastout]
fn main() {
    input!(n: usize, xy: [[isize; 2]; n]);

    let perm = make_permutation(n);
    let mut count = 0;
    let mut sum: f64 = 0.0;
    for v in perm {
        for i in 0..v.len() - 1 {
            sum += (((xy[v[i]][0] - xy[v[i + 1]][0]) * (xy[v[i]][0] - xy[v[i + 1]][0])
                + (xy[v[i]][1] - xy[v[i + 1]][1]) * (xy[v[i]][1] - xy[v[i + 1]][1]))
                as f64)
                .sqrt();
        }
        count += 1;
    }
    println!("{}", sum / count as f64);
}

fn make_permutation(n: usize) -> Vec<Vec<usize>> {
    let mut vecs: Vec<Vec<usize>> = vec![Vec::new(); factorial(n)];
    let nums: Vec<usize> = (0..n).collect();
    let indexes: Vec<usize> = (0..factorial(n)).collect();
    push_recusive(nums, indexes, &mut vecs);
    vecs
}

fn push_recusive<T: Clone>(
    nums: Vec<T>,
    indexes: Vec<usize>,
    vecs: &mut Vec<Vec<T>>,
) -> &mut Vec<Vec<T>> {
    if nums.len() == 0 {
        return vecs;
    }
    let block_size = factorial(nums.len() - 1);
    for (block_index, num) in nums.iter().enumerate() {
        for inner_index in 0..block_size {
            let index = indexes[block_size * block_index + inner_index];
            vecs[index].push(num.clone());
        }
        let new_nums = {
            let mut tmp = nums.clone();
            tmp.remove(block_index);
            tmp
        };
        let new_indexes: Vec<usize> = {
            let slice = &indexes[(block_size * block_index)..(block_size * (block_index + 1))];
            slice.to_vec()
        };
        push_recusive(new_nums, new_indexes, vecs);
    }
    vecs
}

fn factorial(i: usize) -> usize {
    if i <= 1 {
        1
    } else {
        (2..=i).fold(1, |acc, x| acc * x)
    }
}


Measured memory_bytes: 6512
import sys
sys.setrecursionlimit(10**5)

n = int(input())
e = [[] for i in range(n)]
for i in range(1,n):
    x = int(input())
    e[x-1].append(i)

def dfs(x):
    count = len(e[x])
    if count == 0:
        return 0
    l = []
    for nex in e[x]:
        l.append(dfs(nex))
    l.sort(reverse=True)
    now = count
    for i in range(count):
        now = max(now,l[i]+i+1)
    return now
print(dfs(0))

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

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vector<int>> mi;
typedef vector<vector<pair<int, int>>> w_graph;
typedef vector<vector<int>> uw_graph;

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
   	#ifdef DEBUG
		freopen("out.txt", "w", stdout);
	#endif

	ll dp[(int)1e5 + 5];
	int n, W;
	cin >> n >> W;
	int w[105], v[105];
	for (int i = 0; i < n; i++) cin >> w[i] >> v[i];
	
	for (int i = 0; i < 1e5 + 5; i++) dp[i] = 1e15;
	
	dp[0] = 0;
	for (int i = 0; i < n; i++){
		for (int j = 1e5 + 5; j >= 0; j--){
			if (j >= v[i]){
				dp[j] = min(dp[j], dp[j - v[i]] + w[i]);
			}
		}
	}
	ll max_val = 0;
	for (ll i = 0; i < 1e5 + 5; i++){
		if (dp[i] <= W) max_val = max(max_val, i);
	}
	cout << max_val << endl;

	return 0;
}


Measured memory_bytes: 1024
import java.util.*;

public class Main {

    private static final int INF = 2_000_000_000;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] h = new int[N];
        for (int i = 0; i < N; i++) {
            h[i] = sc.nextInt();
        }
        int[][] dp = new int[N][K];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < K; j++) {
                dp[i][j] = INF;
            }
        }
        for (int j = 0; j < K; j++) {
            dp[0][j] = 0;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < K; j++) {
                if (i >= j+1) {
                    int pi = i-(j+1);
                    int min = INF;
                    for (int pj = 0; pj < K; pj++) {
                        min = Math.min(min, dp[pi][pj]);
                    }
                    dp[i][j] = min + Math.abs(h[i]-h[pi]);
                }
            }
        }

        int ans = INF;
        for (int j = 0; j < K; j++) {
            ans = Math.min(ans, dp[N-1][j]);
        }

        System.out.println(ans);
    }
}



Measured memory_bytes: 77512
//------------------------------>> tsukasa_diary's template <<------------------------------//
#include <bits/stdc++.h>
using namespace std;

#define for_(i,a,b) for(int i=(a);i<(b);++i)
#define for_rev(i,a,b) for(int i=(a);i>=(b);--i)
#define allof(a) (a).begin(),(a).end()
#define minit(a,b) memset(a,b,sizeof(a))

using lint = long long;
using pii = pair< int, int >;

template< typename T > using Vec = vector< T >;

template< typename T > bool in_range(T x, T lb, T ub) { return lb <= x && x < ub; }
template< typename T > bool in_range(T x, T y, T lb, T ub) { return in_range(x, lb, ub) && in_range(y, lb, ub); }

template< typename T > void modAdd(T& a, T b, T mod) { a = (a + b + mod) % mod; }
template< typename T > void modMul(T& a, T b, T mod) { a = (a * b) % mod; }
template< typename T > void minUpdate(T& a, T b) { a = min(a, b); }
template< typename T > void maxUpdate(T& a, T b) { a = max(a, b); }

int bitCount(int x) { return __builtin_popcount(x); }
int bitCount(lint x) { return __builtin_popcountll(x); }

const int dx[4] = {0,1,0,-1}, dy[4] = {-1,0,1,0};
const int Dx[8] = {0,1,1,1,0,-1,-1,-1}, Dy[8] = {-1,-1,0,1,1,1,0,-1};
const double EPS = 1e-9;
const double PI = acos(-1);

//--------------8---------------->> coding space <<-----------------8-------------//



int main() {
	string S;
	cin >> S;
	
	int K;
	cin >> K;
	
	int n = S.size();
	for_(i,0,n) {
		int add = (int('z' - S[i]) + 1) % 26;
		if (add <= K) {
			S[i] = 'a';
			K -= add;
		}
	}
	
	S[n-1] = char('a' + (int(S[n-1] - 'a' + K) % 26));
	cout << S << endl;
}
//--------------8---------------->> coding space <<-----------------8-------------//


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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n,m; cin>>n>>m;
	vector<bool>s(n+1,false),g(n+1,false);
	for(int i=0;i<m;++i){
		int a,b; cin>>a>>b;
		if(a==1)s.at(b)=true;
		if(b==n)g.at(a)=true;
	}
	for(int i=1;i<=n;++i){
		if(s.at(i)&&g.at(i)){
			cout<<"POSSIBLE\n"s;
			return 0;
		}
	}
	cout<<"IMPOSSIBLE\n"s;
}


Measured memory_bytes: 3632
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


def main():
    X = input()

    que = queue.LifoQueue()
    cnt = 0
    rest_T = 0
    for x in X:
        if x == 'S':
            que.put(x)
            cnt += 1
        elif x == 'T' and cnt > 0:
            _ = que.get()
            cnt -= 1
        else:
            rest_T += 1

    print(rest_T + cnt)


if __name__ == '__main__':
    main()


Measured memory_bytes: 49736
from math import ceil

N, H = map(int, input().split())
a, b = [], []
for _ in range(N):
    ta, tb = map(int, input().split())
    a.append(ta)
    b.append(tb)

Ma = max(a)
b = sorted(filter(lambda x: x > Ma, b), reverse=True)
lb = len(b)

t = 0
while t < lb:
    H -= b[t]
    t += 1
    if H <= 0:
        break

if H > 0:
    t += ceil(H / Ma)

print(t)


Measured memory_bytes: 12084
//https://atcoder.jp/contests/abc144/tasks/abc144_b
#include <bits/stdc++.h>;
#define ll long long int
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll n;
	cin>>n;
	ll i;
	ll j;
	vector <ll> lis;
	ll p;
	for(i=1;i<=9;i++)
	{
		for(j=1;j<=9;j++)
		{
			p=i*j;
			lis.push_back(p);
			p=0;
		}
	}
	ll x;
	x=lis.size();
	ll cnt=0;
	for(i=0;i<x;i++)
	{
		if(n==lis[i])
		{
			cnt=cnt+1;
		}
		else
		{
			cnt=cnt;
		}
	}
	if(cnt>=1)
	{
		cout<<"Yes"<<"\n";
	}
	else
	{
		cout<<"No"<<"\n";	
	}
	
	return 0;
}

Measured memory_bytes: 3588
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
#define MAXH 1010
#define MAXW 1010
#define MAXN 11
#define INF 10000000
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int H, W, N;
char field[MAXH][MAXW];
pair<int, int> goal[MAXN];
int main(void) {
    cin >> H >> W >> N;
    for (int i = 0; i < H; i++)
        for (int j = 0; j < W; j++)
            cin >> field[i][j];
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            int x = field[i][j] - '0';
            if (1 <= x && x <= N) {
                goal[x] = make_pair(i, j);
            } else if (field[i][j] == 'S') {
                goal[0] = make_pair(i, j);
            }
        }
    }
    int ret = 0;
    for (int a = 0; a < N; a++) {
        int d[H][W];
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                d[i][j] = INF;
        queue<int> X;
        queue<int> Y;
        X.push(goal[a].second); Y.push(goal[a].first);
        d[goal[a].first][goal[a].second] = 0;
        while (!X.empty()) {
            int x = X.front(); X.pop();
            int y = Y.front(); Y.pop();
            if (x == goal[a+1].second && y == goal[a+1].first) {
                ret += d[y][x];
                break;
            }
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (0 <= nx && nx < W && 0 <= ny && ny < H && d[ny][nx] == INF && field[ny][nx] != 'X') {
                    d[ny][nx] = d[y][x] + 1;
                    X.push(nx);
                    Y.push(ny);
                }
            }
        }
    }
    cout << ret << endl;
    return 0;
}

Measured memory_bytes: 6108
#![allow(unused_imports)]
#![allow(non_snake_case)]
use proconio::marker::*;
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        s: String,
        t: String,
    }
    let mut res = Vec::with_capacity(s.len());
    for i in 0..=s.len() - t.len() {
        let mut c = 0;
        for k in 0..t.len() {
            if s.chars().nth(i + k) != t.chars().nth(k) {
                c += 1;
            }
        }
        res.push(c);
    }
    println!("{}", res.iter().min().unwrap())
}


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

using static Input;
using static Util;
class Program
{
    static string S;
    static string T;

    static void INPUT()
    {
        S = NextString();
        T = NextString();
    }

    static void OUT()
    {
        var b = false;
        for (int i = 0; i < S.Length; i++)
        {
            if (S[i] != T[i]) b = true;
        }
        Console.WriteLine(b ? "No" : "Yes");
    }
    static void Main(string[] args)
    {
#if DEBUG  
        //TESTINPUT();
        INPUT();

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

    static void TESTINPUT()
    {
    }

}

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

class Util
{

}




Measured memory_bytes: 17636
#include <algorithm>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define DEBUG 1
using namespace std;
constexpr int kMod = 1000000007;
typedef long long LL;

struct Edge {
  int from;
  int to;
  LL cost;
};

// detect closed-loop -> return false,  else return true.
bool belman_ford(int s, int V, const vector<Edge>& es, vector<LL>* dists) {
  vector<LL> d(V, LLONG_MAX);
  d[s] = 0;

  for (int i = 0; i < V; ++i) {
    bool update = false;
    for (const Edge& e : es) {
      if (d[e.from] == LLONG_MAX) continue;
      if (d[e.to] > d[e.from] + e.cost) {
        d[e.to] = d[e.from] + e.cost;
        update = true;
        if (i == V-1 && e.to == V-1) return false;
      }
    }
    // finish
    if (!update) {
      *dists = d;
      return true;
    }
  }
  *dists = d;
  return true;
}

int main() {
  int N, M; cin >> N >> M;
  vector<Edge> es;
  for (int i = 0; i < M; ++i) {
    int a, b, c; cin >> a >> b >> c;
    --a, --b;
    es.push_back({a, b, -c});
  }

  vector<LL> d;
  if (belman_ford(0, N, es, &d)) {
    cout << -d[N-1] << endl;
  } else {
    cout << "inf" << endl;
  }
}


Measured memory_bytes: 384
# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate,permutations, combinations,combinations_with_replacement,product

def resolve():

    n=int(input())
    d,x=map(int,input().split())
    A=[int(input()) for i in range(n)]

    val=x

    for i in range(n):
        for j in range(d+1):
            if A[i]*j+1<=d:
                val+=1

    print(val)

resolve()

Measured memory_bytes: 3060
input = readlines()

n, m = input.shift.chomp.split("\s").map{|x| x.to_i}

h_list = input.shift.chomp.split("\s").map{|x| x.to_i}

list = {}
input.each do |l|
  a, b = l.chomp.split("\s").map{|x| x.to_i}
  list[a] = [] if list[a].nil?
  list[b] = [] if list[b].nil?
  list[a].push(b)
  list[b].push(a)
end

cnt = 0
(1..n).each do |k|
  h_me = h_list[k - 1]
  is_good = true
  list[k].to_a.each do |b|
    is_good = false if h_list[b - 1] >= h_me
  end
  cnt += 1 if is_good
end

puts cnt


Measured memory_bytes: 39104
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = s; i < (ll)(n); i++)
typedef long long ll;
typedef vector<vector<ll>> vvl;
typedef vector<ll> vl;
typedef vector<vector<char>> vvc;
typedef vector<char> vc;
typedef pair<ll,ll> pll;
ll max(ll x,ll y){
if(x>y)return x;
else return y;
}
ll min(ll x,ll y){
  return x+y-max(x,y);
}


int main() {
  int n,m,c;
  cin >> n >> m >> c;
  vl b(m);
  rep(i,m)cin >> b[i];
  int ans=0;
  rep(i,n){
    vl a(m);
    int sou=c;
    rep(j,m){
      cin >> a[j];
      sou+=a[j]*b[j];
    }
    if(sou>0)ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys


def solve(K: int, S: int):
    ans = 0
    ## TLE
    # for i in range(K+1):
    #     for j in range(K+1):
    #         for r in range(K+1):
    #             if(i+j+r == S):
    #                 ans += 1

    for i in range(K+1):
        for j in range(K+1):
            r = S - i - j 
            if(0 <= r <= K):
                ans += 1

    print(ans)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    solve(K, S)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
import java.util.*;

public class Main{
    
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        long A = sc.nextLong();
        long B = sc.nextLong();
        long[] x = new long[N];
        for(int i = 0; i < N; i++){
            x[i] = sc.nextLong();
        }
        sc.close();

        long sum = 0;

        for(int i = 0; i < N-1; i++){
           sum += Math.min(B, (x[i+1]-x[i])*A);
        }

        System.out.println(sum);
    }
}

Measured memory_bytes: 60140
#include<stdio.h>
int main(void)
{
	long int S;
	int min = 1000, S2 = 0;
	int base = 753;
	scanf("%ld", &S);
	while (S > 100) {
		S2 = S % 1000;
		S /= 10;
		if (S2 >= 753) {
			if (min > S2 - 753) {
				min = S2 - 753;
			}
		}
		else if (S2 < 753) {
			if (min > 753 - S2) {
				min = 753 - S2;
			}
		}
	}
	printf("%d", min);
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main(){
  int x;
  cin>>x;
  vector<int> dp(100005,0);
  dp.at(0)=1;
  for(int i=1;i<100005;++i){
    for(int j=0;j<6;++j){
      if(i-(100+j)>=0 && dp.at(i-(100+j))==1){
        dp.at(i)=1;
      }
    }
  }
  cout<<dp.at(x)<<endl;
  return 0;
}

Measured memory_bytes: 640
#include <iostream>
//#include <iomanip>
//#include <algorithm>
//#include <numeric>
//#include <queue>
//#include <stack>
//#include <math.h>
#include <vector>
//#include <unordered_map>
//#include <string>
//typedef long long LL;
//typedef long double LD;
using namespace std;

int main() {
    int n;
    vector<int> p;
    int tmp_p;
    int ans=0;
    int min_value;
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> tmp_p;
        p.push_back(tmp_p);
    }
    min_value=p[0];
    ans++;
    for(int i=1; i<n; i++){
        if(min_value>=p[i]){
            ans++;
            min_value=p[i];
        }
    }
    cout << ans << endl;
    return 0;
}

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

public class Main{
	public static void main(String[] args){
		try{
			new Main();
		}catch(IOException e){
			e.printStackTrace();
		}
	}

	public Main() throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String line;

		byte[] pat = puzzle();

		while((line = in.readLine()) != null){
			String[] dst = line.split(" ");
			int size = dst.length;
			int[] data = new int[size];
			for(int i=0; i<size; i++){
				data[i] = Integer.parseInt(dst[i]);
			}

			System.out.println(pat[toNum(data)]-1);
		}
	}

	public byte[] puzzle(){
		List<int[]> que = new ArrayList<int[]>();
		byte[] pat = new byte[16434825];
		int[] init = new int[]{0, 1, 2, 3, 4, 5, 6, 7};
		pat[toNum(init)] = 1;
		que.add(init);
		int[][] swap = new int[][]{
				{0, 1}, {1, 2}, {2, 3},
				{4, 5}, {5, 6}, {6, 7},
				{0, 4}, {1, 5}, {2, 6}, {3, 7}
		};

		while(que.size() != 0){
			int[] item = que.get(0);
			que.remove(0);
			int c = pat[toNum(item)]+1;
			for(int i=0; i<10; i++){
				if(item[swap[i][0]]==0 || item[swap[i][1]]==0){
					int[] dst = deepClone(item);
					int t = dst[swap[i][0]];
					dst[swap[i][0]] = dst[swap[i][1]];
					dst[swap[i][1]] = t;
					int index = toNum(dst);
					if(pat[index] == 0){
						pat[index] = (byte)c;
						que.add(dst);
					}
				}
			}
		}
		return pat;
	}

	public int toNum(int[] data){
		int x = 0;
		for(int i=0; i<data.length; i++){
			x <<= 3;
			x += data[i];
		}

		return x;
	}

	public int[] deepClone(int[] data){
		int n = data.length;
		int[] a = new int[n];
		for(int i=0; i<n; i++){
			a[i] = data[i];
		}
		return a;
	}
}

Measured memory_bytes: 27000
#include <bits/stdc++.h>
using namespace std;
const int INF=1000000000;
const int MAX_N=50;
const int MAX_M=50;
typedef pair<int,int> P;
char maze[MAX_N][MAX_N+1];
int N,M;
int sx,sy;
int gx,gy;
int d[MAX_N][MAX_N];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int bfs(){
  cin>>N>>M;
  sx=0;
  sy=0;
  gx=N-1;
  gy=M-1;
  int count=0;
  for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
      cin>>maze[i][j];
      if(maze[i][j]=='.')count++;
    }
  }
  if(maze[0][0]=='#'||maze[gx][gy]=='#')return -1;
  queue<P>que;
  for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
      d[i][j]=INF;
    }
  }
  que.push(P(sx,sy));
  d[sx][sy]=0;
  while(que.size()){
    P p=que.front();que.pop();
    if(p.first==gx&&p.second==gy)break;
    for(int i=0;i<4;i++){
      int nx=p.first+dx[i],ny=p.second+dy[i];
      if(0<=nx&&nx<N&&0<=ny&&ny<M&&maze[nx][ny]!='#'&&d[nx][ny]==INF){
        que.push(P(nx,ny));
        d[nx][ny]=d[p.first][p.second]+1;
      }
    }
  }
  return count-(d[gx][gy]+1);
}
int main(){
  int kotae=bfs();
  if(kotae<0)cout<<-1<<endl;
  else cout<<kotae<<endl;
  return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
ins = lambda: input().rstrip()
ini = lambda: int(input().rstrip())
inm = lambda: map(int, input().split())
inl = lambda: list(map(int, input().split()))
out = lambda x: print('\n'.join(map(str, x)))

n, k = inm()
count = 1
ans = 0
while count <= n:
    count *= k
    ans += 1
print(ans)

Measured memory_bytes: 8976
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repi(i, s, n) for (int i = (s); i < (n); i++)
#ifdef LOCAL
#define INPUT_FILE                    \
  ifstream in("abc150/abc150_d.txt"); \
  cin.rdbuf(in.rdbuf());
#else
#define INPUT_FILE
#endif
#define CIN_OPTIMIZE \
  cin.tie(0);        \
  ios::sync_with_stdio(false);
typedef pair<int, int> P;
typedef long long ll;
const int INF = 100100100;
const int MOD = 1e9 + 7;

ll gcd(ll a, ll b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

int main() {
  INPUT_FILE CIN_OPTIMIZE;

  int N;
  ll M;
  cin >> N >> M;

  vector<ll> a(N);
  set<int> checker;

  rep(i, N) {
    cin >> a[i];
    int t = a[i], cnt = 0;
    while (t % 2 == 0) {
      t /= 2;
      cnt++;
    }
    checker.insert(cnt);
  }
  if (checker.size() != 1) {
    cout << 0 << endl;
    return 0;
  }

  ll l = 1;
  rep(i, N) { l = lcm(l, a[i] / 2); }

  cout << (M < l ? 0 : (M / l + 1) / 2) << endl;
}

Measured memory_bytes: 1024
using System;
using System.Collections.Generic;

class Program {
  static void Main(string[] args) {
    string n = Console.ReadLine();
    int N = int.Parse(n);

    var map = new Dictionary<int, bool>();
    
    for (int i=0; i<N; i++) {
      string s = Console.ReadLine();
      int v = int.Parse(s);
      bool b;
      if (map.TryGetValue(v, out b)) {
        map.Remove(v);
      } else {
        map.Add(v, true);
      }
    }

    Console.WriteLine(map.Count);
  }
}

Measured memory_bytes: 18144
import java.util.*;

public class Main {

    public long[] solve(int N) {
        double x, y, z;
        boolean found = false;
        long[] ret = new long[3];
        for (double i = 1; i <= 3500; i++) {
            for (double j = 1; j <= 3500; j++) {
                x = 4 * i * j - N * i - N * j;
                y = N * i * j;
                z = y / x;
                if ((y % x) == 0 && z > 0) {
                    return new long[]{ (long)i, (long)j, (long)z };
                }
            }
        }
        return new long[]{0,0,0};
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Main obj  = new Main();
        long[] ret = obj.solve(n);
        System.out.println(ret[0]+" "+ret[1]+" "+ret[2]);
    }
}

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

int main() {
	string N;
  	cin >> N;
  
  	ll sum=0;
  	for (long i=0; i<(long)(N.length()); ++i) {
      char cbuff=N[i];
      	sum += atol(&cbuff);
    }
  
  	if (sum%9L) {
      cout << "No" << endl;
    } else {
      cout << "Yes" << endl;
    }
    return 0;
}

Measured memory_bytes: 3712
import collections

num = int(input())
votes = []
for i in range(num):
  votes.append(input())
  
c = collections.Counter(votes)

max_freq = c.most_common()[0][1]

words = []
for word, freq in c.items():
  if freq == max_freq:
    words.append(word)

words = sorted(words)
for word in words:
    print(word)

Measured memory_bytes: 45120
#include<bits/stdc++.h>
using namespace std;
int main(){
  int H,W;
  cin>>H>>W;
  vector<string>S(H);
  for(int i=0; i<H; i++){
    cin>>S[i];}
  
  int count=0;
  for(int i=0; i<H; i++){
    for(int j=0; j<W; j++){
      if(S[i][j]=='.'){
        count=0;  //ここでcountを再度宣言。
        for(int k=max(0,i-1); k<min(H,i+2); k++){  //  この数値範囲での処理なら、
          for(int l=max(0,j-1); l<min(W,j+2); l++){ // 8方向全てに'#'があるか検索できる。
            if(S[k][l]=='#'){  // '#'があるとき、count++して、
              count++;}
          }
        S[i][j]=count+'0';}  // その数を元のS[i][j]に代入する。
      }
    }
  }  //計算処理はここで終了。'.'のみ処理するだけで、'#'に手は付けない。
  for(int i=0; i<H; i++){
    cout<<S[i]<<endl;}  // 処理結果を出力する。
}


Measured memory_bytes: 256
s = input()
s = list(s)
ans = 1 << 99
for c in range(ord('a'), ord('z') + 1):
    c = chr(c)
    t = s.copy()
    while not all(c == cc for cc in t):
        for i in range(len(t)):
            if c in t[i:i+2]:
                t[i] = c
        t.pop()
    ans = min(ans, len(s) - len(t))
print(ans)


Measured memory_bytes: 3060
'''
https://atcoder.jp/contests/abc084/tasks/abc084_d
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 1000000007

    def primecheck(n):
        p = [True] * (n + 1)
        p[0] = False
        p[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if p[i]:
                for j in range(i * i, n + 1, i):
                    p[j] = False
        return p
    
    p = primecheck(10**5)
    cnt = 0
    res = [0]*(10**5)
    for i in range(10**5):
        if p[i]==p[(i+1)//2]==1:
            cnt += 1
        res[i] = cnt


    q = int(input())
    for _ in range(q):
        l, r = map(int, input().split())
        print(res[r]-res[l-1])

if __name__ == '__main__':
    main()


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

using namespace std;
typedef long long ll;
const int MAXN = 3010;
const ll MOD = 998244353;

int A, B, C, D;
ll dp[MAXN][MAXN]; // i rows and max j
ll dps[MAXN][MAXN];

int main()
{
    ios_base::sync_with_stdio(0);

    cin >> A >> B >> C >> D;
    dp[A][B] = 1;
    for (int i = A; i <= C; i++)
    {
        for (int j = 1; j <= D; j++)
        {
            dps[i][j] = (dps[i][j] + (i - 1) * dps[i][j-1]) % MOD;
            dp[i][j] = (dp[i][j] + dps[i][j]) % MOD;
        }

        for (int j = B; j <= D; j++)
        {
            dp[i+1][j] += (j - 1) * dp[i][j];
            dp[i+1][j] %= MOD;

            dps[i+1][j] += dp[i][j];
        }
    }
    ll ans = 0;
    for (int j = 1; j <= D; j++)
    {
        ans *= C;
        ans += dp[C][j];
        ans %= MOD;
    }

    cout << ans << "\n";
}

Measured memory_bytes: 144652
#include <iostream>
#include <cstdio>

using namespace std;

int main()
{
    int n;
    double denominator = 0.0;

    cin >> n;

    for(int i = 0; i < n; ++i)
    {
        int a;
        cin >> a;

        denominator += 1.0 / a;
    }

    printf("%.6lf\n", 1.0 / denominator);
}

Measured memory_bytes: 256
import math
import sys

def insertion_sort(a, n, g):
    ct = 0
    for i in range(g,n):
        v = a[i]
        j = i-g
        while j >= 0 and a[j] > v:
            a[j+g] = a[j]
            j = j-g
            ct += 1
        a[j+g] = v
    return ct

n = int(input())
a = list(map(int, sys.stdin.readlines()))
m = 0
b = 0
ct= 0
g = []
while True:
    b = 2.25*b+1
    if b > n:
        break
    g.append(math.ceil(b))
    m += 1
g = g[::-1]

for i in g:
    ct += insertion_sort(a, n, i)

print(m)
print(*g, sep=" ")
print(ct)
print(*a, sep="\n")

Measured memory_bytes: 118500
void main()
{
    long k, s;
    rdVals(k, s);

    long cnt;
    foreach (x; 0 .. k+1)
    {
        foreach (y; 0 .. k+1)
        {
            long z = s - x - y;
            if (0 <= z && z <= k) ++cnt;
        }
    }

    cnt.writeln;
}

enum long mod = 10^^9 + 7;
enum long inf = 1L << 60;

T rdElem(T = long)()
if (!is(T == struct))
{
    return readln.chomp.to!T;
}

alias rdStr = rdElem!string;
alias rdDchar = rdElem!(dchar[]);

T rdElem(T)()
if (is(T == struct))
{
    T result;
    string[] input = rdRow!string;
    assert(T.tupleof.length == input.length);
    foreach (i, ref x; result.tupleof)
    {
        x = input[i].to!(typeof(x));
    }
    return result;
}

T[] rdRow(T = long)()
{
    return readln.split.to!(T[]);
}

T[] rdCol(T = long)(long col)
{
    return iota(col).map!(x => rdElem!T).array;
}

T[][] rdMat(T = long)(long col)
{
    return iota(col).map!(x => rdRow!T).array;
}

void rdVals(T...)(ref T data)
{
    string[] input = rdRow!string;
    assert(data.length == input.length);
    foreach (i, ref x; data)
    {
        x = input[i].to!(typeof(x));
    }
}

void wrMat(T = long)(T[][] mat)
{
    foreach (row; mat)
    {
        foreach (j, compo; row)
        {
            compo.write;
            if (j == row.length - 1) writeln;
            else " ".write;
        }
    }
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.traits;
import std.container;
import std.functional;
import std.typecons;
import std.ascii;
import std.uni;

Measured memory_bytes: 256
/* In the name of Allah */

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define LL_INF 1LL << 62
#define INF 1 << 30
#define SetBit(x, k) (x |= (1LL << k))
#define ClearBit(x, k) (x &= ~(1LL << k))
#define CheckBit(x, k) (x & (1LL << k))
#define mod 1000000007

int n;
ll x[100005][3];
ll dp[100005][3];

ll solve(int pos, int prev){
  if(pos >= n) return 0;

  if(prev != -1 && dp[pos][prev] != -1) return dp[pos][prev];

  ll res = 0;
  for(int i = 0; i < 3; i++){
    if(i == prev) continue;
    res = max(res, x[pos][i]+solve(pos+1, i));
  }
  
  return dp[pos][prev] = res;
}

int main()
{
  memset(dp, -1, sizeof dp);
  cin >> n;
  for(int i = 0; i < n; i++)
    cin >> x[i][0] >> x[i][1] >> x[i][2];

  cout << solve(0, -1) << "\n";

  return 0;
}

Measured memory_bytes: 16008
#include <iostream>
#include <cstdio>

//#define PI 3.141592653589

using namespace std;



int main()
{
	int n, a[100];
	
	cin >> n;
	for (int i=0; i<n; i++) cin >> a[i];
	for (int i=n-1; i>=0; i--)
	{
		if (i != 0)
			cout << a[i] << " ";
		else
			cout << a[i] << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1160
#include "bits/stdc++.h"
using namespace std;

int main(int argc, char const *argv[])
{
	int n, k;
	cin >> n >> k;
	long long ans = 0;
	for(int i = k+1; i <= n; i++) {
		ans += 1LL * (n / i) * (i - k);
		if(n % i != 0) {
			if((n % i) >= k) {
				ans += (n % i) - k + 1;
				if(k == 0) ans--;
				// cout << i << " " << (n % i) - k + 1 << endl;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In,' '));
        }

        public void Solve(ConsoleInput cin)
        {
            var A = cin.ReadInt;
            var B = cin.ReadInt;
            var C = cin.ReadInt;

            var ans = A + B;
            if(ans > B + C){
                ans = B + C;
            }
            if(ans > A + C){
                ans = A + C;
            }
            WriteLine(ans);
        }
    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream,char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }

        public string Read
        {
            get
            {
                if(inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for(int i = 0;i < tmp.Length;i++)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }

        
        public string ReadLine { get { return _stream.ReadLine(); }}
        public int ReadInt { get { return int.Parse(Read); }}
        public long ReadLong { get { return long.Parse(Read); }}
        public double ReadDouble { get { return double.Parse(Read); }}
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret;}
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret;}
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret;}
    }

}


Measured memory_bytes: 13268
#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define ALL(s) s.begin(),s.end()
const int M=100010;
int INF=1000000007;
using ll=long long;


int main(){
	int n,m,R;cin>>n>>m>>R;
	int r[8];rep(i,0,R)cin>>r[i];
	int a,b,c;

	//自己連結は0.経路のない場合INF;
	ll dp[220][220]={};
	rep(i,1,n+1)rep(j,1,n+1)
		if(i!=j)dp[i][j]=INF;
	rep(i,0,m){
		//経路を入力;
		cin>>a>>b>>c;
		dp[a][b]=dp[b][a]=c;
	}
	rep(k,1,n+1){
		rep(i,1,n+1){
			rep(j,1,n+1){
				//iからjに行く道と,
				//kを経由していく道の最短距離を調べる.
				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
			}
		}
	}
	ll ans=INF;
	sort(r,r+R);
	do {
		ll count=0;
		rep(i,0,R-1)
			count+=dp[r[i]][r[i+1]];
		ans=min(ans,count);
	}while(next_permutation(r,r+R));
	cout<<ans<<endl;
}

Measured memory_bytes: 640