akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

int h,w;
vs a;

vvi f(){
	vs a_(h);
	vvi b(h,vi(w)),c(h,vi(w));
	for(int i=0;i<h;i++){
		int t=0;
		for(int j=0;j<w;j++){
			if(a[i][j]=='.'){
				t++;
				if(i&&a[i-1][j]=='.') b[i][j]=b[i-1][j]+1;
				else b[i][j]=1;
				c[i][j]=t+b[i][j]-1;
			}
			else t=0;
		}
	}
	for(int i=0;i<h;i++) for(int j=0;j<w;j++) a_[i]+=a[h-i-1][w-j-1];
	a=a_;
	return c;
}

int main(){
	cin>>h>>w;
	a=vs(h);
	for(int i=0;i<h;i++) cin>>a[i];
	vvi b=f(),c=f();
	int res=0;
	for(int i=0;i<h;i++) for(int j=0;j<w;j++) res=max(res,b[i][j]+c[h-i-1][w-j-1]-1);
	cout<<res<<endl;
}

Measured memory_bytes: 55552
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pi acos(-1)
#define mod 998244353
using namespace std;


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

    string s;
    cin >> s;
    cout << s[0] << s[1] << s[2];
}


Measured memory_bytes: 3652
S = str(input())
N = len(S)
L = list(S)
L = set(L)
if N != 26: #含まないものがある
  for i in range(26):
    temp = chr(i+97)
    if temp not in L:
      ans = S+temp
      print(ans)
      exit()
M = []
All = [chr(97+i) for i in range(26)]
#print(All)
for i in range(25):
  now = 25-i
  M.append(S[now])
  if S[now] > S[now-1]:
    M.sort()
    for x in M:
      if x > S[now-1]:
        temp = x
        ans = S[:now-1]+temp
        print(ans)
        exit()
  
print(-1)  

Measured memory_bytes: 9156
while True:
    a,op,b = input().split()
    a = int(a)
    b = int(b)
    if op == '?':
        break
    if op == '+':
        print(a+b)
    elif op == '-':
        print(a-b)
    elif op == '*':
        print(a*b)
    elif op == '/':
        print(a//b)


Measured memory_bytes: 5596
import copy
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
S = [[1 if a == '.' else 0 for a in list(input())]  for _ in range(H)]

def main():
    R = copy.deepcopy(S)
    for h in range(H):
        s = 0
        for w in range(W):
            if R[h][w] == 1:
                s += 1
                R[h][w] = s
            else:
                s = 0
        l = 0
        for w in range(W-1, -1, -1):
            if R[h][w] > 0:
                l = max(l, R[h][w])
                R[h][w] = l
            else:
                l = 0

    L = copy.deepcopy(S)
    for w in range(W):
        s = 0
        for h in range(H):
            if L[h][w] == 1:
                s += 1
                L[h][w] = s
            else:
                s = 0
        l = 0
        for h in range(H-1, -1, -1):
            if L[h][w] > 0:
                l = max(l, L[h][w])
                L[h][w] = l
            else:
                l = 0
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, L[h][w]+R[h][w]-1)
    print(ans)

if __name__ == "__main__":
    main()

Measured memory_bytes: 140552
import java.io.*; 
import java.math.*;
import java.util.*;
import java.awt.Point;
 
public class Main {
	static final long MOD = 998244353L;
	//static final long INF = -1000000000000000007L;
	//static final long MOD = 1000000007L;
	//static final int INF = 1000000007;
	
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		PrintWriter pw = new PrintWriter(System.out);
		int X = sc.ni();
		boolean[] dp = new boolean[100001];
		dp[0] = true;
		for (int i = 100; i <= 100000; i++) {
			boolean val = dp[i-100]||dp[i-101]||dp[i-102]||dp[i-103]||dp[i-104]||dp[i-105];
			dp[i] = val;
		}
		if (dp[X])
			pw.println(1);
		else
			pw.println(0);
		pw.close();
 	}
    
    public static int[][] sort(int[][] array) {
    	//Sort an array (immune to quicksort TLE)
		Random rgen = new Random();
		for (int i = 0; i < array.length; i++) {
		    int randomPosition = rgen.nextInt(array.length);
		    int[] temp = array[i];
		    array[i] = array[randomPosition];
		    array[randomPosition] = temp;
		}
		Arrays.sort(array, new Comparator<int[]>() {
			  @Override
        	  public int compare(int[] arr1, int[] arr2) {
				  return arr1[0]-arr2[0]; //ascending order
	          }
		});
		return array;
	}
    
    public static long[][] sort(long[][] array) {
    	//Sort an array (immune to quicksort TLE)
		Random rgen = new Random();
		for (int i = 0; i < array.length; i++) {
		    int randomPosition = rgen.nextInt(array.length);
		    long[] temp = array[i];
		    array[i] = array[randomPosition];
		    array[randomPosition] = temp;
		}
		Arrays.sort(array, new Comparator<long[]>() {
			  @Override
			  //Descending order
        	  public int compare(long[] arr1, long[] arr2) {
				  if (arr2[0] < arr1[0])
					  return -1;
				  if (arr2[0] > arr1[0])
					  return 1;
				  return 0;
	          }
		});
		return array;
	}
    
    static class FastScanner { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastScanner() { 
            br = new BufferedReader(new InputStreamReader(System.in)); 
        } 
  
        String next() { 
            while (st == null || !st.hasMoreElements()) { 
                try { 
                    st = new StringTokenizer(br.readLine());
                } catch (IOException  e) { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int ni() { 
            return Integer.parseInt(next()); 
        } 
  
        long nl() { 
            return Long.parseLong(next()); 
        } 
  
        double nd() { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() { 
            String str = ""; 
            try { 
                str = br.readLine(); 
            } catch (IOException e) {
                e.printStackTrace(); 
            } 
            return str; 
        }
    }
}

Measured memory_bytes: 21588
x=int(input())
lst=[100,101,102,103,104,105]
dp=[0]*(x+1)
dp[0]=1
for u in lst:
    h=dp[:]
    for i in range(u,x+1):
        if dp[i-u]==1 or h[i-u]==1:
            h[i]=1
    dp=h
if dp[x]==1:
    print(1)
else:
    print(0)

Measured memory_bytes: 4596
n = int(input())

c = [[0] * 10 for _ in range(10)] * n
for i in range(1, n + 1):
    i1 = i // 10 ** (len(str(i)) - 1)
    i2 = i % 10
    c[i1][i2] += 1
#
cnt = 0
for i in range(10):
    for j in range(10):
       cnt += c[i][j] * c[j][i]
print(cnt)


Measured memory_bytes: 56556
import java.util.Scanner;

public class Main {
	public static final int inf = 100000000;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt();
		int n = sc.nextInt();
		int[] a = new int[n];
		int[] b = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
			b[i] = sc.nextInt();
		}
		int[][] dp = new int[1001][20000];
		for (int i = 0; i < 20000; i++) {
			dp[0][i] = inf;
		}
		for (int i = 0; i < 1001; i++) {
			dp[i][0] = 0;
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= h; j++) {
				if(j-a[i]<=0) {
					dp[i+1][j] = Math.min(dp[i][j],b[i]);
				}else {
					dp[i+1][j] = Math.min(dp[i][j],dp[i+1][j-a[i]]+b[i]);
				}
			}
		}
		System.out.println(dp[n][h]);
		sc.close();
	}
}

Measured memory_bytes: 131620
# B - Magic 2
def main():
    A, B, C, K = map(int, open(0).read().split())
    for _ in range(K):
        if A >= B:
            B *= 2
        else:
            C *= 2
    print("Yes" if A < B < C else "No")


if __name__ == "__main__":
    main()


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

using namespace std;
using ll = long long;
const ll mod = 1000000007;


int main()
{
    ll n;
    cin >> n;
    ll ans = (n / 500) * 1000;
    n %= 500;
    ans += (n / 5) * 5;
    cout << ans << endl;
}

Measured memory_bytes: 256
//g++ -std=c++14 test.cpp -o test.out
//ある文字列の一部分に、ある文字が含まれているかどうかを知る
//→
//各文字ごとに、その位置を格納するという考え方
//setの使い方
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <map> 
#include <utility>
#include <limits.h>
#include <bitset>
#include <set>
using namespace std;
 
#define LL long long int
const LL INF = (LL)(1e18)+1;
const int INF_INT = 2147483647;
const LL mod = 1000000007ll;

int N;
int Q;
string S;
//i個目のクエリの、type、i、cをそれぞれquery[i][0],query[i][1],query[i][2]とする
int query[20000][3];

vector<int> ans;
 
void solve(){
	vector<set<int>> char_position(26);//a~zの位置を格納
	for(int i=0;i<N;i++){
		char_position[S[i]-'a'].insert(i);
	}
	for(int i=0;i<Q;i++){
		if(query[i][0]==1){
			//普通に上書き
			char_position[S[query[i][1]-1]-'a'].erase(query[i][1]-1);
			S[query[i][1]-1] = (char)query[i][2];
			char_position[S[query[i][1]-1]-'a'].insert(query[i][1]-1);
		}else{
			int numof_char = 0;
			for(int j=0;j<26;j++){
				int left = query[i][1]-1;
				int right = query[i][2];
				auto lower_index = char_position[j].lower_bound(left);
				if(lower_index!=char_position[j].end() && *lower_index<right){
					numof_char++;
				}
			}
			ans.push_back(numof_char);
		}
	}
}
 
int main(){
	cin >> N;
	cin >> S;
	cin >> Q;
	for(int i=0;i<Q;i++){
		cin >> query[i][0] >> query[i][1];
		if(query[i][0]==1){
			char c;
			cin >> c;
			query[i][2] = (int)c;
		}else{
			cin >> query[i][2];
		}
	}
 
	solve();
 
	for(int i=0;i<ans.size();i++) cout << ans[i] << endl;
	return 0;
}

Measured memory_bytes: 24708
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll inf = 1000000000;
typedef pair<ll, ll> P;
P p[100005];
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		ll x, l;
		cin >> x >> l;
		p[i] = make_pair(x + l, x - l);
	}
	sort(p, p + n);
	ll ans = 0;
	ll kai = -inf;
	for (int i = 0; i < n; i++) {
		if (kai > p[i].second)continue;
		ans++;
		kai = p[i].first;
	
	}
	cout << ans << endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;
typedef long long ll;
using namespace std;
const ll mod=1000000007,mod9=1000000009;
template <class T>inline T lcm(T a,T b){return (a*b/__gcd(a,b));}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin>>n;
    cout<< (n-1)*n/2<<endl;
    return 0;
}



Measured memory_bytes: 256
package main

import (
	"fmt"
	"math"
	"strconv"
)

// ColorCode is a string like #rrggbb
type ColorCode string

// ColorName is a name of color
type ColorName string

// Color has colorname and colorcode
type Color struct {
	name ColorName
	code ColorCode
}

// ColorTable has default colors
type ColorTable struct {
	colors []Color
}

var (
	colorTable = ColorTable{
		[]Color{
			Color{"black", "#000000"},
			Color{"blue", "#0000ff"},
			Color{"lime", "#00ff00"},
			Color{"aqua", "#00ffff"},
			Color{"red", "#ff0000"},
			Color{"fuchsia", "#ff00ff"},
			Color{"yellow", "#ffff00"},
			Color{"white", "#ffffff"},
		},
	}
)

func main() {
	var code ColorCode
	fmt.Scanf("%s", &code)
	for {
		if code == "0" {
			break
		}
		name := colorTable.getNearestColor(code)
		fmt.Println(name)
		fmt.Scanf("%s", &code)
	}
}

func (colorstr ColorCode) parseColorValue() (float64, float64, float64) {
	rr, gg, bb := colorstr[1:3], colorstr[3:5], colorstr[5:7]
	rri, err1 := strconv.ParseUint(string(rr), 16, 8)
	ggi, err2 := strconv.ParseUint(string(gg), 16, 8)
	bbi, err3 := strconv.ParseUint(string(bb), 16, 8)
	if err1 != nil || err2 != nil || err3 != nil {
		err := fmt.Errorf(
			"Failed to read color strings, color code:%s, err: %v %v %v",
			colorstr, err1, err2, err3)
		panic(err)
	}
	return float64(rri), float64(ggi), float64(bbi)
}

func (table *ColorTable) getNearestColor(targetcode ColorCode) ColorName {
	var nearestColor ColorName
	var nearestValue = 1e5
	for _, v := range table.colors {
		trr, tgg, tbb := targetcode.parseColorValue()
		prr, pgg, pbb := v.code.parseColorValue()
		// diff := math.Sqrt(
		// 	math.Pow(prr-trr, 2) + math.Pow(pgg-tgg, 2) + math.Pow(pbb-tbb, 2))
		diff := math.Pow(prr-trr, 2) +
			math.Pow(pgg-tgg, 2) +
			math.Pow(pbb-tbb, 2)
		if nearestValue > diff {
			nearestValue = diff
			nearestColor = v.name
		}
	}
	return nearestColor
}



Measured memory_bytes: 1236
n = int(input())
a_list = [int(input()) for _ in range(n)]

visited = [False] * n

here = 0
for i in range(n):
    visited[here] = True
    moveto = a_list[here] - 1

    if moveto == 1:
        print(i+1)
        exit()

    if visited[moveto]:
        break

    here = moveto

print("-1")
exit()

Measured memory_bytes: 50116
n,m,x,y = map(int, input().split())
x_list = list(map(int, input().split()))
y_list = list(map(int, input().split()))
x_list.sort()
y_list.sort()
ans = min(y_list[0], y) - max(x_list[-1], x)
if ans >= 1:
    print("No War")
else:
    print("War")

Measured memory_bytes: 3188
/**
    AUTHOR:JUNSH
    TIME:19/5/25
**/
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rev(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll;
inline int read(){
    int f=1,x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return f*x;
}
const int inf=0x3f3f3f3f;
int a[55];
int n,k;
int cal(int l,int r){
    int cnt=0;
    int sum=0;
    int valid[55];
    rep(i,1,l-1){
        valid[++cnt]=a[i];
    }
    rep(i,r,n){
        valid[++cnt]=a[i];
    }
    if(cnt>k)return -1;
    int regert=k-cnt;
    sort(valid+1,valid+cnt+1);
    rep(i,1,regert){
        if(valid[i]<0)valid[i]=0;
        else break;
    }
    rep(i,1,cnt){
        sum+=valid[i];
    }
    return sum;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    rep(i,1,n)cin>>a[i];
    int ans=0;
    rep(l,1,n){
        rep(r,l,n+1){
            ans=max(ans,cal(l,r));
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
//#include<cmath>
#include<array>
#include<algorithm>
//#include<deque>
#include<vector>
//#include<utility>
//#include<set>
//#include<map>
//#include<list>
//#include<bitset>

using namespace std;
using LLI = long long int;
LLI N;

//array<int, 8>dir_x = { 0,0,1,1,1,-1,-1,-1 };
//array<int, 8>dir_y = { 1,-1,1,0,-1,1,0,-1 };
//array<int, 4>dir_x2 = { 0,0,1,-1 };
//array<int, 4>dir_y2 = { 1,-1,0,0 };
//char alp[] = { 'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z' };

//class UnionFind {
//public:
//	vector<int>data;
//	UnionFind(int size) :data(size, -1) {};
//	bool unionset(int x, int y) {
//		x = root(x), y = root(y);
//		if (x != y) {
//			if (data[y] < data[x]) {
//				swap(x, y);
//			}
//			data[x] += data[y];
//			data[y] = x;
//		}
//		return x != y;
//	}
//	bool findset(int x, int y) {
//		return root(x) == root(y);
//	}
//	int root(int x) {
//		return data[x] < 0 ? x : data[x] = root(data[x]);
//	}
//	int size(int x) {
//		return -data[root(x)];
//	}
//};

//LLI gcd(LLI x, LLI y) {
//	LLI  r;
//	if (x < y) {
//		swap(x, y);
//	}
//	r = x % y;
//	while (r != 0) {
//		x = y;
//		y = r;
//		r = x % y;
//	}
//	return y;
//}
//LLI lcm(LLI x, LLI y) {
//	return x / gcd(x, y) * y;
//}

//long nCr(int n, int r) {
//	long ans = 1;
//	for (int i = n; i > n - r; i--) {
//		ans = ans * i;
//	}
//	for (int i = 1; i < r + 1; i++) {
//		ans = ans / i;
//	}
//	return ans;
//}

//const int n_max = 8;
//array<array<bool, n_max>, n_max>graph;
//int dfs(int v,int N,array<bool,n_max>visited) {
//	int ret = 0;
//	bool all_visited = true;
//	for (int i = 0; i < N;i++) {
//		if (visited[i] == false) {
//			all_visited = false;
//		}
//	}	
//	if (all_visited) {
//		return 1;
//	}
//	for (int i = 0; i < N;i++) {
//		if (graph[v][i] == false) {
//			continue;
//		}
//		if (visited[i] == true) {
//			continue;
//		}
//		visited[i] = true;
//		ret += dfs(i,N,visited);
//		visited[i] = false;
//	}
//	return ret;
//}

//vector<vector<int>>sub;
//int dfs(int id) {
//	if (sub[id].size() == 0) {
//		return 1;
//	}
//	int minP = (int)1e9;
//	int maxP = 0;
//	for (int i : sub[id]) {
//		int P = dfs(i);
//		minP = min(minP, P);
//		maxP = max(maxP, P);
//	}
//	return minP + maxP + 1;
//}

//#define debug(x) cerr << #x << " : " << x << endl
//#define debugv(x) cerr << #x << " : "; for(auto i:x) cerr << i << ", "; cerr<<endl

int main(void) {
	LLI A, B, C,K;
	string S;
	vector<LLI>vec(4);
	cin >> N >> K >> S;
	if (S[K - 1] == 'A') {
		S[K - 1] = 'a';
	}
	else if (S[K - 1] == 'B') {
		S[K - 1] = 'b';
	}
	else if (S[K - 1] == 'C') {
		S[K - 1] = 'c';
	}
	cout << S << endl;
}


Measured memory_bytes: 256
def main():
    N, K = map(int, input().split())
    V = [int(v) for v in input().split()]

    m = 0 
    r = min(N, K)
    for a in range(r+1):
        for b in range(r+1-a):
            if b == 0:
                v = V[:a]
            else:
                v = V[:a] + V[-b:]
            v.sort()    
            for i in range(K+1-a-b):
                if i >= len(v):
                    break
                if  v[i] >= 0:
                    break
            s = sum(v[i:])
            if s > m:
                m = s

    print(m)


main()


Measured memory_bytes: 3064
#! /usr/bin/env python3

from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations

A, B, N = [int(_) for _ in input().split()]

x = min(B-1, N) # 0 <= x < B and 0 <= x <= N
a = (A * x) // B - A * (x // B)

print(int(a))   

Measured memory_bytes: 10416
#include "bits/stdc++.h"

using namespace std;

template <int p>
struct Modint
{
	int value;

	Modint() : value(0) {}
	Modint(long x) : value(x >= 0 ? x % p : (p + x % p) % p) {}

	inline Modint &operator+=(const Modint &b)
	{
		if ((this->value += b.value) >= p)
			this->value -= p;
		return (*this);
	}
	inline Modint &operator-=(const Modint &b)
	{
		if ((this->value += p - b.value) >= p)
			this->value -= p;
		return (*this);
	}
	inline Modint &operator*=(const Modint &b)
	{
		this->value = (int)((1LL * this->value * b.value) % p);
		return (*this);
	}
	inline Modint &operator/=(const Modint &b)
	{
		(*this) *= b.inverse();
		return (*this);
	}

	Modint operator+(const Modint &b) const { return Modint(*this) += b; }
	Modint operator-(const Modint &b) const { return Modint(*this) -= b; }
	Modint operator*(const Modint &b) const { return Modint(*this) *= b; }
	Modint operator/(const Modint &b) const { return Modint(*this) /= b; }

	inline Modint &operator++(int) { return (*this) += 1; }
	inline Modint &operator--(int) { return (*this) -= 1; }

	inline bool operator==(const Modint &b) const { return this->value == b.value; }
	inline bool operator!=(const Modint &b) const { return this->value != b.value; }
	inline bool operator<(const Modint &b) const { return this->value < b.value; }
	inline bool operator<=(const Modint &b) const { return this->value <= b.value; }
	inline bool operator>(const Modint &b) const { return this->value > b.value; }
	inline bool operator>=(const Modint &b) const { return this->value >= b.value; }

	//requires that "this->value and p are co-prime"
	// a_i * v + a_(i+1) * p = r_i
	// r_i = r_(i+1) * q_(i+1) * r_(i+2)
	// q == 1 (i > 1)
	// reference: https://atcoder.jp/contests/agc026/submissions/2845729 (line:93)
	inline Modint inverse() const
	{
		assert(this->value != 0);
		int r0 = p, r1 = this->value, a0 = 0, a1 = 1;
		while (r1)
		{
			int q = r0 / r1;
			r0 -= q * r1;
			swap(r0, r1);
			a0 -= q * a1;
			swap(a0, a1);
		}
		return Modint(a0);
	}

	friend istream &operator>>(istream &is, Modint<p> &a)
	{
		long t;
		is >> t;
		a = Modint<p>(t);
		return is;
	}
	friend ostream &operator<<(ostream &os, const Modint<p> &a)
	{
		return os << a.value;
	}
};

const int MOD = 998244353;

using Int = Modint<MOD>;

Int pow(Int e, int x)
{
	if (x == 0) return 1;
	Int res = (x & 1 ? e : 1), tmp = pow(e, x>>1);
	res *= tmp * tmp;
	return res;
}

void solve(void)
{
	int n, sum = 0;
	cin >> n;
	vector<int> as(n);
	for (int& a : as)
	{
		cin >> a;
		sum += a;
	}
	int m = sum+1;
	vector<Int> dp(m), dp2(m);
	dp[0] = dp2[0] = 1;
	for (int a : as)
	{
		vector<Int> nx(m), nx2(dp2);
		for (int i = 0; i < m; i++)
		{
			int na = a + i;
			if (na < m)
			{
				nx[na] += dp[i];
				nx2[na] += dp2[i];
			}
			nx[i] += dp[i] * 2;
		}
		swap(nx, dp);
		swap(nx2, dp2);
	}
	Int ans = pow(Int(3), n) - (sum & 1 ? 0 : (dp[sum/2]-dp2[sum/2])*3);
	for (int i = sum / 2 + 1; i <= sum; i++)
	{
		ans -= dp[i]*3;
	}
	cout << ans << endl;
}

int main()
{
	solve();
	//cout << "yui(*-v・)yui" << endl;
	return 0;
}


Measured memory_bytes: 1704
#include<bits/stdc++.h>
using namespace std;
#define fr(dt,i,a,b) for(dt i=a;i<b;i++)
#define f0(a,b) for(int i=a;i<b;i++)
#define fn(b,a) for(int i=b;i>a;i--)
#define dbg(x); cout<<"\n"<<#x<<": "<<x;
#define ret return
#define pb push_back
#define pf push_front
#define fastIO(); ios_base::sync_with_stdio(false); cin.tie(NULL);
#define UL9 1000000007
#define UL5 100007
#define INF 1e9+7
#define PI 3.1415926
#define sq(a) (a)*(a)
#define fs first
#define sd second
typedef vector<long long int> vlli;
typedef vector<int> vi;
typedef map<char,int> mci;
typedef long long int lli;  //  e-18 to e18
int main(){
    fastIO();
    string s;
    cin>>s;
    if(s=="ABC") cout<<"ARC\n";
    else cout<<"ABC\n";
    ret 0; 
}                                                             

Measured memory_bytes: 3656
// 
//#define DEBUG

#ifndef DEBUG

#include <stdio.h>

#else

#include "stdafx.h"

#endif // DEBUG



#include <stdio.h>

int main()
{
	int x,result;

	scanf("%d", &x);

	result = x * x *x;

	printf("%d\n", result);



	/***************************************/
	#ifndef DEBUG

	#else
		_gettch();
	#endif
	/***************************************/

	return 0;
}

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

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    int n;
    pair<int64_t, int> p[2000];
    cin >> n;
    for(int i=0;i<n;++i){
        int a;
        cin >> a;
        p[i] = {a, i};
    }
    sort(p, p+n, greater());
    static int64_t dp[2001][2001];
    for(int i=0;i<=n;++i) for(int j=0;j<=n;++j) dp[i][j] = 0;
    for(int i=0;i<n;++i){
        for(int j=0;j<=i;++j){
            int b = n - 1 - i + j;
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + p[i].first * abs(p[i].second - j));
            dp[i+1][j  ] = max(dp[i+1][j  ], dp[i][j] + p[i].first * abs(p[i].second - b));
        }
    }
    int64_t ans = dp[n][0];
    for(int i=1;i<=n;++i) ans = max(ans, dp[n][i]);
    cout << ans << endl;
    
    return 0;
}

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

int main() {
    int N;
    int count = 0;
    cin >> N;
    int m = N / 2 + 1;
    for (int i = 1; i < m; i++) {
        int tmp = N - i;
        if (i != tmp) count ++;
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll          long long
#define int 		long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define ff           first
#define ss           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
using namespace std;

bool possible(vi &prefa,vi &prefb,int mid,int k){
	int n = sz(prefa);
	int m = sz(prefb);
	rep(i,0,mid+1){
		if (i<n && mid-i<m){
			if (prefa[i]+prefb[mid-i]<=k){
				//cout<<mid<<" "<<i<<" "<<prefa[i]<<" "<<mid-i<<" "<<prefb[mid-i]<<endl;
				return true;
			}
		}
	}
	return false;
}
int32_t main(){
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	//insert code
	int n,m,k;
	cin>>n>>m>>k;
	vi prefa(n+1,0);
	vi prefb(m+1,0);
	int x;
	rep(i,1,n+1){
		cin>>x;
		prefa[i] = prefa[i-1]+x;
	}
	rep(i,1,m+1){
		cin>>x;
		prefb[i] = prefb[i-1]+x;
	}
	int start = 0, end = n+m;
	int ans = 0;
	while (start<=end){
		int mid = (start+end)/2;
		if (possible(prefa,prefb,mid,k)){
			ans = mid;
			start = mid+1;
		}
		else end = mid-1;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 6360
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}

int main(void){
  SPEEDUP
  cout << setprecision(15);
  string s;cin >> s;
  stack<char> st;
  rep(i,s.length()){
    if(s[i] == 'B'){
      if(!st.empty()) st.pop();
    }else st.push(s[i]);
  }
  vector<char> v;
  while(!st.empty()){
    v.push_back(st.top());
    st.pop();
  }
  per(i,v.size()) cout << v[i];
  cout << endl;
  return 0;
}


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

int main() {
    vector<int> v(9);
    int N;
    cin >> N;
    for(int i = 0; i < N; ++i) {
        int a;
        cin >> a;
        a = min(a, 3200);
        v[a / 400] += 1;
    }
    int res = 0;
    for(int i = 0; i < 8; ++i) {
        res += v[i] > 0;
    }
    int mi = res + (res == 0 && v[8] > 0);
    int ma = res + v[8];
    cout << mi << ' ' << ma << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>				//edit by thidailoc
using namespace std;				//team three wolves
typedef long long ll;
typedef vector<ll> vi;
#define fu(i,a,b)   for(ll i=a;i<b;i++)
#define fd(i,b,a)   for(ll i=b;i>=a;i--)
#define pb(i)	    push_back(i)
#define popb()    	pop_back()
#define sc(a) 	    scanf("%lld",&a)
#define sc2(a,b)    scanf("%lld%lld",&a,&b)
#define pr(a)	    printf("%lld ",a)
#define pr2(a,b)    printf("%lld %lld",a,b)
#define lowb(a,n,x) lower_bound(a,a+n,x) -a
#define lowb2(a,x)	lower_bound(a.begin(),a.end(),x) -a.begin()
#define all(x) 		(x).begin(), (x).end()
#define sz(a) 		(ll)a.size()
#define le			length()						
#define re 			return 	
#define debug(x)    cerr << #x << " = " << x << endl
#define INPUT       freopen("locin.txt", "r", stdin)
#define OUTPUT      freopen("locout.txt", "w", stdout)

double const eps = 1e-6;	//dung trong sai so
ll const Base=1e9+7;
ll arr[1000000],mark[1000][1000];

ll Solves(){
//	INPUT;
	ll n,m,k,cnt=0,ans=0,x,a,b,c;
	// PROCESSING IN HERE
	sc2(n,m);
	while(m--){
		sc2(a,b);
	//	if(mark[a][b]==0){
			arr[a]++;
			arr[b]++;
			mark[a][b]=mark[b][a]=1;
	//	}
	}
	fu(i,1,n+1)cout<<arr[i]<<endl;
	re 0;
}


int main(){
	Solves();
}

Measured memory_bytes: 2432
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,n) for(ll i=a;i<n;i++)
#define rev(i,n,a) for(ll i=n-1;i>=a;i--)
#define f first
#define s second
#define vll vector<ll>
#define vvll vector<vector<ll>>
#define vpii vector<pair<int,int>>
#define vpll vector<pll>
#define pll pair<ll,ll>
#define secreterror() ios_base::sync_with_stdio(false);cin.tie(NULL);

void solve(){

    ll n,k;
    cin>>n>>k;

    vector<ll>pre(n+5,0);

    vector<ll>arr(n+1);

    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }

    ll logn=min((ll)41,(k));

    for(int k=0;k<logn;k++){
        for(int i=1;i<=n;i++){
            ll x=ceil(double(i)-0.5-double(arr[i]));
            ll y=floor(double(i)+0.5+double(arr[i]));

            x=max((ll)0,x);
            y=min(n,y);

            pre[x]++;
            pre[y+1]--;
        }

        for(int i=1;i<=n+3;i++){

            pre[i]=pre[i]+pre[i-1];

        }

        for(int i=1;i<=n;i++){
            arr[i]=pre[i];
        }

        for(int i=0;i<=n+3;i++){
            pre[i]=0;
        }


       
    }






    

    for(int i=1;i<=n;i++){
        cout<<arr[i]<<" ";
    }
    cout<<endl;
    
}


int main()
{
    secreterror()
    // ll t;
    // cin>>t;
    //while(t--){
        solve();
        
    //}

}

Measured memory_bytes: 6372
H, W = [int(x) for x in input().split()]
board = [['.']*(W+2)]
for _ in range(H):
    board.append(['.'] + [x for x in input()] + ['.'])
board.append(['.']*(W+2))
   
cnt = 0
for i in range(1, H+1):
    for j in range(1, W):
        if board[i][j] == '#' and board[i][j+1] != '#' and board[i][j-1] != '#' and board[i-1][j] != '#' and board[i+1][j] != '#':
            cnt += 1

print('No') if cnt else print('Yes')

Measured memory_bytes: 3064
def solve(N, Y):
    for a in range(N + 1):
        for b in range(N + 1 - a):
            c = N - (a + b)
            if a * 10000 + b * 5000 + c * 1000 == Y:
                return a, b, c
    return -1, -1, -1


N, Y = [int(n) for n in input().split()]
print(*solve(N, Y))


Measured memory_bytes: 3060
#define _USE_MATH_DEFIMES
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

const int MOD = 1'000'000'007;
const int INF = 1'000'000'000; //1e9
const int NIL = -1;
const long long LINF = 1'000'000'000'000'000'000; // 1e18
const long double EPS = 1E-10;

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






class UnionFind{
    int n;
    std::vector<int> par;//根ならマイナス*要素数

public:
    UnionFind(): n(0){}
    UnionFind(int N): n(N), par(n){
        for(int i(0); i < n; ++i){
            par[i] = -1;
        }
    }

    void resize(int N){
        n = N;
        par.resize(n, -1);
    }

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

    bool unit(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return false;

        if(-par[x] < -par[y]) std::swap(x, y); 
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    bool same(int x, int y){
        return find(x) == find(y);
    }

    int howmany(int x){ //同じグループに属すものの個数(自分を含む)
        return -par[find(x)];
    }

    std::vector<std::vector<int>> groups(){
        std::vector<int> root_buf(n), group_size(n);
        for(int i(0); i < n; ++i){
            root_buf[i] = find(i);
            ++group_size[root_buf[i]];
        }
        std::vector<std::vector<int>> ret(n);
        for(int i(0); i < n; ++i){
            ret[i].reserve(group_size[i]);
        }
        for(int i(0); i < n; ++i){
            ret[root_buf[i]].push_back(i);
        }
        ret.erase(
            std::remove_if(std::begin(ret), std::end(ret),
                [&](const std::vector<int>& v){return v.empty();}),
            std::end(ret));
        return ret;
    }
};

int main(){
    int N, M; std::cin >> N >> M;
    UnionFind uf(N);
    {
        int A, B;
        for(int i(0); i < M; ++i){
            std::cin >> A >> B;
            uf.unit(A-1, B-1);
        }
    }
    int ans(-1);
    for(int i(0); i < N; ++i){
        if(i == uf.find(i)) ++ans;
    }
    std::cout << ans << std::endl;
    return 0;
}


Measured memory_bytes: 3784
#include<map>
#include<string>
#include<vector>
#include<iostream>
#include<algorithm>

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

using namespace std;

struct Letter{
	bool re;
	int num;
	string s;
};

Letter L[100000];
bool used[100000];
map< pair<string,int>,vector<int> > Pos;
map< pair<string,int>,vector<int> >::iterator it;
vector<int>::iterator jt;

void dfs(int i){
	used[i]=true;
	printf("%d\n",i+1);

	if(i>0 && L[i-1].re && !used[i-1]) dfs(i-1);

	pair<string,int> next(L[i].s,L[i].num+1);
	if((it=Pos.find(next))!=Pos.end()){
		jt=lower_bound(it->second.begin(),it->second.end(),i);
		if(jt!=it->second.begin()){
			int j=*--jt;
			it->second.erase(jt);
			dfs(j);
			return;
		}
	}
}

int main(){
	for(int n;cin>>n,n;){
		Pos.clear();
		rep(i,n){
			used[i]=false;
			string s; cin>>s;

			bool re;
			if(*s.rbegin()=='v'){
				re=true;
				s.erase(--s.end());
			}
			else re=false;

			int j;
			for(j=(int)s.length()-1;j>=0&&isdigit(s[j]);j--);
			int num=-1;
			if(j<(int)s.length()-1) num=atoi(s.c_str()+j+1);
			s=s.substr(0,j+1);

			L[i]=(Letter){re,num,s};

			if(L[i].num>1) Pos[make_pair(L[i].s,L[i].num)].push_back(i);
		}

		rep(i,n) if(!L[i].re && L[i].num<=1 && !used[i]) dfs(i);
	}

	return 0;
}

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

using namespace std;

int main(void){
    int n,k;
    cin >> n >> k;
    int cost = 0;
    int arr[n] = {0};
    for (int i=0;i<n;i++){
        cin >> arr[i];
    }

    vector <int> dp(n, INT_MAX);
    dp[0] = 0;

    for (int i=0;i<n;i++){
        for (int j=i+1;j<=(i+k);j++){
            if(j < n){
                dp[j] = min(dp[j], (dp[i] + abs(arr[i] - arr[j])));
            }
        }
    }
    cout << dp[n-1] << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
#include <stdlib.h>//random,NULL
#include <string.h>
#include <time.h>
#include <unistd.h>//sleep()
#include <math.h>
#include <stdbool.h>

#define rep(i,n) for(int i=0; i<((int)n); i++)
#define REP(i,n) for(int i=0; i<=((int)n); i++)
#define srep(i,a,n) for(int i=a; i<((int)n); i++)
#define SREP(i,a,n) for(int i=a; i<=((int)n); i++)
#define rrep(i,n) for(int i=n-1; i>=0; i--)
#define RREP(i,n) for(int i=n; i>=0; i--)
#define INF 1000000000


bool prime_judge(int a){
  if((int)sqrt(a)<2){
    return true;
  }
  else{
    int flag=1;
    srep(i,2,(int)sqrt(a)+1){
      if(a%i==0){
        flag=0;
        break;
      }
    }
    if(flag==1){
      return true;
    }
    else{
      return false;
    }
  }
}

//N!に含まれる素数aの個数
int prime_number(int a, int N){
  int temp=a;
  int count=0;
  while(temp<=N){
    count+=N/temp;
    temp=temp*a;
  }
  return count;
}


int main(){
  char buf[1024];
  int N;

  fgets(buf,sizeof(buf),stdin);
  sscanf(buf, "%d", &N);

  int *prime=(int *)malloc(sizeof(int)*N);
  int element=0;
  srep(i,2,N+1){
    bool temp=prime_judge(i);
    if(temp==true){
      prime[element]=i;
      element++;
    }
    else{
      ;
    }
  }

  int *prime_n=(int *)malloc(sizeof(int)*N);
  rep(i,element){
    prime_n[i]=prime_number(prime[i], N);
  }

  // rep(i,element){
  //   printf("prime[%d] = %d\n", i, prime[i]);
  // }
  // rep(i,element){
  //   printf("prime_n[%d] = %d\n", i, prime_n[i]);
  // }


  int count=0;
  if(prime_n[0]>=74){
    count++;
  }

  int ncount_2=0;
  int ncount_4=0;
  int ncount_14=0;
  int ncount_24=0;
  rep(i,element){
    if(prime_n[i]>=2){
      ncount_2++;
    }
    if(prime_n[i]>=4){
      ncount_4++;
    }
    if(prime_n[i]>=14){
      ncount_14++;
    }
    if (prime_n[i]>=24){
      ncount_24++;
    }
  }

  // printf("ncount_2 = %d\n", ncount_2);
  // printf("ncount_4 = %d\n", ncount_4);
  // printf("ncount_14 = %d\n", ncount_14);
  // printf("ncount_24 = %d\n", ncount_24);

  count+=ncount_24*(ncount_2-1);
  count+=ncount_14*(ncount_4-1);
  if(ncount_4>1){
    count+=ncount_4*(ncount_4-1)*(ncount_2-2)/2;
  }

  printf("%d\n", count);

  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <utility>
using namespace std;
typedef pair<int, int> p;
int h, w;
string s[55];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int d[55][55];
int ans;
queue<p> que;
int main() {
	cin >> h >> w;
	for (int i = 0; i < h; i++)for (int j = 0; j < w; j++)d[i][j]=-1;
	for (int i = 0; i < h; i++)cin >> s[i];
	que.push(make_pair(0, 0));
	d[0][0] = 1;
	while (!que.empty()) {
		p fs = que.front();
		que.pop();
		int x = fs.first;
		int y = fs.second;
		for (int i = 0; i < 4; i++) {
			int wx = x + dx[i];
			int wy = y + dy[i];
			if (wx > -1 && wx<h&&wy>-1 && wy < w&&d[wx][wy]==-1&&s[wx][wy] == '.') {
				que.push(make_pair(wx, wy));
				d[wx][wy] = d[x][y] + 1;
			}
		}
	}
	ans = d[h - 1][w - 1];
	if (ans == -1) {
		cout << -1;
		return 0;
	}
	int u = 0;

	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (s[i][j] == '.')u++;
		}
	}
	
	cout << u - ans;
}

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

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

Measured memory_bytes: 256
# -*- coding: utf-8 -*- coding: utf-8 -*-
mod = 10**9 + 7

n, m = map(int, raw_input().split())
x = map(int, raw_input().split())
y = map(int, raw_input().split())

sx = sum(x)
sy = sum(y)
zx = 0
zy = 0
for i, xi in enumerate(x):
    zx += sx - (n - i)*xi
    sx -= xi
    zx %= mod
for i, yi in enumerate(y):
    zy += sy - (m - i)*yi
    sy -= yi
    zy %= mod
print zx*zy % mod


Measured memory_bytes: 14496
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    long long N, D, X;
    cin >> N >> D >> X;
    
    long long ans = 0;
    for (int i = 0; i < N; i++){
        int A;
        cin >> A;

        int d = 1;
        while(d <= D){
            ans++;
            d += A;
        }
    }

    cout << ans + X << endl;
}

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

vector<int> Centroid(int root, const vector<vector<int>> &g, const vector<bool> &dead) {
        int alive_cnt = 0;
        map<int, int> alive_node;
        //{ 
                function<void (int, int)> count_alive = [&](int u, int prev) {
                        alive_node[u] = alive_cnt ++;
                        for (auto v : g[u]) if (v != prev && !dead[v]) {
                                count_alive(v, u);
                        }
                };
                count_alive(root, -1);
        //}
        vector<int> centroid;
        vector<int> sz(alive_cnt);
        function<void (int, int)> dfs = [&](int u, int prev) {
                int x = alive_node[u];
                sz[x] = 1;
                bool is_centroid = true;
                for (auto v : g[u]) if (v != prev && !dead[v]) {
                        dfs(v, u);
                        int y = alive_node[v];
                        sz[x] += sz[y];
                        if (sz[y] > alive_cnt / 2) is_centroid = false;
                }
                if (alive_cnt - sz[x] > alive_cnt / 2) is_centroid = false;
                if (is_centroid) centroid.push_back(u);
        };
        dfs(root, -1);
        return centroid;
}

int main() {
        int n;
        scanf("%d", &n);
        vector<vector<int>> g(n);
        vector<vector<pair<int ,int>>> gg(n);
        for (int i = 0; i < n - 1; i ++) {
                int a, b, c;
                scanf("%d%d%d", &a, &b, &c);
                a --, b --;
                g[a].push_back(b);
                g[b].push_back(a);
                gg[a].emplace_back(b, c);
                gg[b].emplace_back(a, c);
        }
        long long ans = 0;
        vector<int> sz(n);
        function<void (int, int)> dfs = [&](int u, int prev) {
                sz[u] = 1;
                for (auto e : gg[u]) {
                        int v = e.first, cost = e.second;
                        if (v == prev) continue;
                        dfs(v, u);
                        sz[u] += sz[v];
                        ans += min(sz[v], n - sz[v]) * (long long) 2 * cost;
                }                                 
        };
        dfs(0, -1);
        vector<bool> dead(n);
        auto centroid = Centroid(0, g, dead);
        if (centroid.size() == 1) {
                int mi = 0x3f3f3f3f;
                for (auto e : gg[centroid[0]]) {
                        mi = min(mi, e.second);
                }
                ans -= mi;
        } else {
                for (auto e : gg[centroid[0]]) {
                        if (e.first == centroid[1]) {
                                ans -= e.second;
                                break;
                        }
                }
        }
        printf("%lld\n", ans);
        return 0;
}


Measured memory_bytes: 25984
n = int(input())
i = 1
while i <= n:
    if i % 3 == 0:
        print(' ', end='')
        print(i, end='')
    else:
        x = i
        while x:
            if x % 10 == 3:
                print(' ', end='')
                print(i, end='')
                break
            x = x // 10
    i += 1
print('')


Measured memory_bytes: 6160
#include <algorithm>
#include <bitset>
#include <complex>
#include <cstdio>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

using namespace std;

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

typedef long long ll;

const int Inf = 100100100;
const double EPS = 1e-9;

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

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

int bitCount(long bits) {
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, b;
    cin >> a >> b;
    if ((a * b) % 2 == 0) {
      cout << "No" << '\n';
    } else {
      cout << "Yes" << '\n';
    }

    return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {

	/**
	 * @param args
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		int[][] candy = new int[2][n];
		int[][] dp = new int[2][n];
		
		for(int i = 0; i < 2 ; i++){
			String[] tmpArray = br.readLine().split(" ");
			
			for(int j = 0; j < n; j++){
				candy[i][j] = Integer.parseInt(tmpArray[j]);
			}
		}
		
		dp[0][0] = candy[0][0];
		for(int i = 1; i < n; i++){
			dp[0][i] = candy[0][i] + dp[0][i - 1];
		}
		
		dp[1][0] = dp[0][0] + candy[1][0];
		
		for(int i = 1; i < n; i++){
			dp[1][i] = Math.max(dp[1][i - 1] + candy[1][i], dp[0][i] + candy[1][i]);
		}
		
		System.out.println(dp[1][n-1]);
	}

}


Measured memory_bytes: 23252
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>

using namespace std;
typedef long long LL;
template <typename F, typename S> std::ostream& operator<<(ostream& os, const pair<F,S>& p) {
    os << "(" << p.first << "," << p.second << ")"; return os; }
template <typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "["; for(const T& a: v){ os << a << ", "; } os << "]"; return os; }
template <typename K, typename V> ostream& operator<<(ostream& os, const map<K,V>& m) {
    os << "{"; for(const auto& p: m){ os << p.first <<":"<< p.second << ", "; } os << "}"; return os; }

const LL MOD = 1000000007;

int main(){
    LL n, k;
    cin >> n >> k;
    if(n == 1){
        cout << 1 << endl;
        return 0;
    }
    set<LL> value_set;
    value_set.insert(0);
    for(LL i = 1; ; ++i){
        value_set.insert(i);
        value_set.insert(n/i);
        if(i*i >= n) break;
    }
    vector<LL> values(value_set.begin(), value_set.end());
    LL w = values.size();
    vector<vector<LL>> a(k+1, vector<LL>(w+1));
    for(LL i = 1; i < w; ++i){
        a[0][i] = values[i] - values[i-1];
    }
    for(LL cur = 1; cur <= k; ++cur){
        LL j = 1;
        LL total = 0;
        for(LL i = w-1; i >= 1; --i){
            while(j < values.size() && values[j] * values[i] <= n){
                total = (total + a[cur-1][j]) % MOD;
                ++j;
            }
            a[cur][i] = total * (values[i] - values[i-1]) % MOD;
        }
    }
    cout << a[k][1] << endl;
    return 0;
}



Measured memory_bytes: 54272
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
typedef complex<ld> Point;
const ll mod = 1000000007;
const ll INF = mod * mod;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)

void solve() {
	ll n, a[5];
	cin >> n;
	rep(i, 5) {
		cin >> a[i];
	}
	ll ans = INF;
	ll mi = INF;
	rep(i, 5)mi = min(mi, a[i]);
	ans = (n+mi-1) / mi + 4;
	
	cout << ans << endl;
}
int main() {
	solve();
	//stop
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){
	

  	long long int m,ans,i,n;
  
  	scanf("%lld %lld",&n,&m);
  
  	if(n == 1){
    	printf("%lld\n",m);
      	return 0;
    }
  
  	for(i=m/n;i >=1;i--){
      if(m % i ==0){
      	ans = i;
        break;
      }
    }
	 
  	printf("%lld\n",ans);
  
	return 0;
}


Measured memory_bytes: 128
N, A, B = map(int, input().split())
ans = 0
if (B - A) % 2 == 0:
	ans = (B - A) // 2
else:
	if N - A >= B - 1:
		dis = A - 1 + 1
		ans = dis + ((B-dis) - 1) //2
		
		
	else:
		
		dis = N - B + 1
		ans = dis + (N - (A+dis)) //2

print(ans)

Measured memory_bytes: 3060