akhauriyash/Code-Regression huggingface dataset:
A =input()
B=""
for i in range(len(A)):
    if i==0:
        if A[i]!="B":
            B= B+A[i]
    else:
        if A[i] !="B":
            B=B+A[i]
        else:
            B = B[:(len(B)-1)]
print(B)


Measured memory_bytes: 3060
import java.util.*;
import static java.lang.System.*;

public class Main {

	Scanner sc = new Scanner(in);
	
	Map<String, Set<String>> map = new HashMap<String, Set<String>>();
	Set<String> checked = new HashSet<String>();
	
	void calc(String s) {
		checked.add(s);
		Set<String> set = map.get(s);
		List<String> remove = new ArrayList<String>();
		List<String> add = new ArrayList<String>();
		add.clear();
		remove.clear();
		for (String t : set) {
			if (map.containsKey(t)) {
				if (!checked.contains(t))
					calc(t);
				remove.add(t);
				for (String u : map.get(t))
					add.add(u);
			}
		}
		set.removeAll(remove);
		set.addAll(add);
	}
	
	void run() {
		while (true) {
			int n = sc.nextInt();
			if (n == 0) break;
			map.clear();
			String zero = null;
			for (int i = 0; i < n; i++) {
				StringTokenizer st = new StringTokenizer(sc.next(), ": ,.");
				Set<String> set = new HashSet<String>();
				String s = st.nextToken();
				map.put(s, set);
				if (i == 0) zero = s;
				while (st.hasMoreTokens())
					set.add(st.nextToken());
			}
			checked.clear();
			calc(zero);
			out.println(map.get(zero).size());
		}
	}
	
	public static void main(String[] args) {
		new Main().run();
	}

}

Measured memory_bytes: 33524
#include <algorithm>
#include <utility>
#include <cstdio>
#include <vector>
#define pb push_back
typedef long long ll; 
std::vector<std::pair<int, int> > adj[100005]; 
int x[100005], y[100005], w[100005], dep[100005], sz[100005], mx[100005]; 
void dfs(int u, int fa = -1)
{
	sz[u] = 1; 
	mx[u] = 0; 
	for (auto &e : adj[u])
	{
		int v = e.first; 
		if (v == fa)
			continue; 
		dep[v] = dep[u] + 1; 
		dfs(v, u); 
		sz[u] += sz[v]; 
		mx[u] = std::max(mx[u], sz[v]); 
	}
}
int main()
{
	// freopen("AGC018-D.in", "r", stdin); 
	int n; 
	scanf("%d", &n); 
	for (int i = 1; i < n; i++)
	{
		scanf("%d%d%d", x + i, y + i, w + i); 
		adj[--x[i]].pb({--y[i], w[i]}); 
		adj[y[i]].pb({x[i], w[i]}); 
	}
	dfs(0); 
	ll ans = 0; 
	for (int i = 1; i < n; i++)
	{
		int u = x[i], v = y[i];
		if (dep[u] > dep[v])
			std::swap(u, v); 
		int s = std::min(sz[v], n - sz[v]); 
		if (s << 1 == n)
			ans -= w[i]; 
		ans += 2ll * s * w[i]; 
	}
	for (int u = 0; u < n; u++)
	{
		mx[u] = std::max(mx[u], n - sz[u]); 
		if (mx[u] << 1 < n)
		{
			int mn = 1e9; 
			for (auto &e : adj[u])
				mn = std::min(mn, e.second); 
			ans -= mn; 
		}
	}
	printf("%lld\n", ans);
	return 0; 
}


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

using namespace std;
const int N=2e5+5,mod=1e9+7;
#define ll long long
string s;
int dp[N][5];
void Add(int &ret,int x)
{
    ret+=x;
    if(ret>=mod)
        ret-=mod;
}
int solve(int idx,bool f)
{
    if(idx==(int)s.size()) return 1;
    int &ret=dp[idx][f];
    if(~ret) return ret;
    ret=0;
    for(int i=0;i<=1;i++)
        for(int j=0;j<=1;j++)
            if(i+j<=1&&(f||i+j<=s[idx]-'0'))
                Add(ret,solve(idx+1,f||i+j<s[idx]-'0'));
    return ret;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    memset(dp,-1,sizeof dp);
    cin>>s;
    cout<<solve(0,0)<<endl;
    return 0;
}


Measured memory_bytes: 12240
#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <unordered_map>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>
#include <assert.h>
#include <unordered_map>
#include <fstream>
#include <complex>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef pair<ll,ll> P;
typedef pair<int,int> pii;
typedef vector<P> vpl;
typedef tuple<ll,ll,ll> tapu;
#define rep(i,n) for(int i=0; i<(n); i++)
#define REP(i,a,b) for(int i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int MAX = 510000;
ll dy[8] = {0,-1,0,1,1,-1,1,-1};
ll dx[8] = {1,0,-1,0,1,-1,-1,1};
const double pi = acos(-1);
const double eps = 1e-7;
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){
    if(a>b){
        a = b; return true;
    }
    else return false;
}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){
    if(a<b){
        a = b; return true;
    }
    else return false;
}
template<typename T> inline void print(T &a){
    rep(i,a.size()) cout << a[i] << " ";
    cout << "\n";
}
template<typename T1,typename T2> inline void print2(T1 a, T2 b){cout << a << " " << b << "\n";}
template<typename T1,typename T2,typename T3> inline void print3(T1 a, T2 b, T3 c){
    cout << a << " " << b << " " << c << "\n";
}
const ll mod = 1e9 + 7;
//const int mod = 998244353;

vvl G(101010);
vl a(101010);
vl d(101010,0);

ll dfs(ll u, ll p){
    if(d[u] == 1) return a[u];
    ll sum = 0;
    ll mx = 0;
    for(auto v : G[u]){
        if(v == p) continue;
        ll df = dfs(v,u);
        if(df == -1) return -1;
        chmax(mx, df);
        sum += df;
    }
    ll t;
    if(sum - mx < mx) t = sum - mx;
    else t = sum / 2;
    ll rest = sum - t * 2;
    if(a[u] > sum || a[u] < t + rest) return -1;
    return a[u] - (sum - a[u]);
}

int main(){
    ll n; cin >> n;
    rep(i,n) cin >> a[i];
    rep(i,n-1){
        ll u,v; cin >> u >> v; u--; v--;
        G[u].push_back(v);
        G[v].push_back(u);
        d[u]++; d[v]++;
    }
    if(n == 2){
        if(a[0] == a[1]) puts("YES");
        else puts("NO");
        return 0;
    }
    ll s = 0;
    rep(i,n) if(d[i] >= 2){
        s = i;
        break;
    }
    if(dfs(s,-1) == 0) puts("YES");
    else puts("NO");
}

Measured memory_bytes: 15488
N, X = map(int, input().split())

n_all = [1] + [0] * N
n_p = [1] + [0] * N
for i in range(1, N + 1):
    n_all[i] = n_all[i - 1] * 2 + 3
    n_p[i] = n_p[i - 1] * 2 + 1
    
def f(l, x):
    if l == 0:
        return 0 if x <= 0 else 1
    if x <= 1:
        return 0
    elif x < n_all[l - 1] + 1:
        return f(l - 1, x - 1)
    elif x == n_all[l - 1] + 1:
        return n_p[l - 1]
    elif x < n_all[l - 1] * 2 + 2:
        return n_p[l - 1] + 1 + f(l - 1, x - n_all[l - 1] - 2)
    else:
        return n_p[l - 1] * 2 + 1
      
print(f(N, X))


Measured memory_bytes: 3064
import heapq

n = int(input())
alst = list(map(int, input().split()))

l_s = alst[:n]
r_s = [-1 * num for num in alst[2 * n:]]
heapq.heapify(l_s)
heapq.heapify(r_s)
l_total = [sum(l_s)]
r_total = [sum(r_s)]

for num in alst[n:2*n]:
    if l_s[0] > num:
        l_total.append(l_total[-1])
    else:
        minus = heapq.heappop(l_s)
        heapq.heappush(l_s, num)
        l_total.append(l_total[-1] + num - minus)
        
for num in alst[n:2*n][::-1]:
    if r_s[0] > num * -1:
        r_total.append(r_total[-1])
    else:
        minus = heapq.heappop(r_s)
        heapq.heappush(r_s, -1 * num)
        r_total.append(r_total[-1] - num - minus)

ans = -1 * 10 ** 20
for num, num2 in zip(l_total, r_total[::-1]):
    ans = max(ans, num + num2)
print(ans)

Measured memory_bytes: 42704
using System;
using System.Linq;

namespace CGcdOnBlackboard
{
    class Program
    {
        static void Main(string[] args)
        {
            // 入力の取得
            var n = int.Parse(Console.ReadLine());
            var inputNums = Console.ReadLine().Split().Select(int.Parse).ToArray();

            // 1つの数字を書き換えて、最大公約数が変わり得るのはUNIQUEな数字のみ
            // UNIQUEな数字に対して、その他の数字の最大公約数を計算して、そのうち最大のものが解答
            var numbersWithCount = inputNums.GroupBy(x => x).Select(g => Tuple.Create(g.Key, g.Count())).ToArray();
            var numbers = numbersWithCount.Select(x => x.Item1).ToArray();
            var uniqueNumbers = numbersWithCount.Where(x => x.Item2 == 1).Select(x => x.Item1).ToArray();

            var maxGcd = 0;
            if (uniqueNumbers.Any())
            {
                foreach (var uniqueNum in uniqueNumbers)
                {
                    var otherGcd = numbers.Where(num => num != uniqueNum)
                        .Aggregate((gcd, num) => Gcd(num, gcd));
                    if (maxGcd < otherGcd) maxGcd = otherGcd;
                }
            }
            else
            {
                maxGcd = numbers.Aggregate((gcd, num) => Gcd(num, gcd));
            }

            // 解答の出力
            Console.WriteLine(maxGcd);
        }

        static int Gcd(int a, int b)
        {
            if (a < b) return Gcd(b, a);
            if (0 < b) return Gcd(b, a % b);
            return a;
        }
    }
}


Measured memory_bytes: 27868
#include <iostream>

using namespace std;
int main (){
    int N,T;
    cin >> N >> T;
    int t[N];
    for(int i = 0; i < N; i++){
        cin >> t[i];
    }
    int ans = 0;
    for(int i = 0; i < N-1; i++){
        if(t[i+1] - t[i] > T){
            ans += T;
        }
        else ans += (t[i+1] - t[i]);
    }
    ans += T;
    cout << ans << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define ll long long int

using namespace std;
ll m=1e9+7;
int main(){
    ll n;
    cin>>n;
    ll a[n];
    for(ll i=0;i<n;i++)cin>>a[i];
    ll b[n];
    memset(b,0,sizeof(b));

    b[n-2]=a[n-1];
    for(ll i=n-3;i>=0;i--){
        b[i]=(a[i+1]+b[i+1])%m;
    }
    ll ans=0;
    for(ll i=0;i<n-1;i++){
        ans=(ans+(a[i]*b[i])%m)%m;
    }
    cout<<ans;

    return 0;
}


Measured memory_bytes: 6776
import sys
input = sys.stdin.buffer.readline
from collections import Counter

def main():
    N,M = map(int,input().split())
    a = list(map(int,input().split()))
    cum = [0]
    
    for num in a:
        cum.append((cum[-1]+num)%M)

    c = Counter(cum)
    ans = 0
    
    for it in c.values():
        ans += (it*(it-1))//2
        
    print(ans)
        
if __name__ == "__main__":
    main()


Measured memory_bytes: 56944
#include<iostream>                                                                    
#include<cmath>                                                                          
                                                                                         
using namespace std;                                                                     
                                                                                         
int getDp( int* dp, int i, int K, int* h ) {                                             
   if( dp[ i ] != -1 ) {                                                                 
      return dp[ i ];                                                                    
   }                                                                                     
   dp[ i ] = getDp( dp, i - 1, K, h ) + abs( h[ i ] - h[ i - 1 ] );                      
   for( int j = 2; j <= K && i - j >= 0; j++ ) {                                         
      dp[ i ] = min( getDp( dp, i - j, K, h ) + abs( h[ i ] - h[ i - j ] ),              
                     dp[ i ] );                                                          
   }                                                                                     
   return dp[ i ];                                                                       
}                                                                                        
                                                                                         
int main() {                                                                             
   int N, K;                                                                             
   cin >> N >> K;                                                                        
   int h[ N ];                                                                           
   for( int i= 0; i < N; i++ ) {                                                         
      cin >> h[ i ];                                                                     
   }                                                                                     
                                                                                         
   int dp[ N ];                                                                          
   dp[ 0 ] = 0;                                                                          
   dp[ 1 ] = abs( h[ 0 ] - h[ 1 ] );                                                     
   for( int i = 2; i < N; i++ ) {                                                        
      dp[ i ] = -1;                                                                      
   }                                                                                     
   cout << getDp( dp, N - 1, K, h );                                                     
   return 0;                                                                             
}                                                

Measured memory_bytes: 8832
def read_input():
    D = int(input())
    C = input().split()
    C = [int(i) for i in C]
    S = [list(map(int, input().split())) for _ in range(D)]
    T = [int(input()) for _ in range(D)]
    return D, C, S, T


def scoring(S, D, T, C):
    res = []
    last = [0 for _ in range(26)]
    final = 0
    for i in range(D):
        dec = 0
        last[T[i] - 1] = i + 1
        for j in range(26):
            dec += C[j] * (i - last[j] + 1)
        final += S[i][T[i] - 1] - dec
        res.append(final)
    return res


D, C, S, T = read_input()
res = scoring(S, D, T, C)
for x in res:
    print(x)


Measured memory_bytes: 9352
N,a,b,c = map(int, input().split())
L = [int(input()) for i in range(N)]
m = []
def m_dep(s):
    if len(s) == N:
        if '1' in s and '2' in s and '3' in s:
            m.append(calc([int(i) for i in s]))
    else:
        for i in range(4):
            m_dep(s + str(i))

def calc(l):
    A=0
    B=0
    C=0
    M=0
    for i,n in enumerate(l):
        if n==1:
            if A!=0:
                M+=10
            A+=L[i]
        if n==2:
            if B!=0:
                M+=10
            B+=L[i]
        if n==3:
            if C!=0:
                M+=10
            C+=L[i]
    M += abs(a-A)+abs(b-B)+abs(c-C)
    return(M)


m_dep('')
print(min(m))


Measured memory_bytes: 5000
#include <bits/stdc++.h>
#define ll long long
#define MAX_N 8
using namespace std;

int n,m;
bool G[MAX_N][MAX_N];
bool visited[MAX_N];

int dfs(int u, bool visited2[MAX_N]){
    bool flag = true;
    for(int i =0; i < n; i++){
        if( !visited2[i] ){
            flag = false;
            break;
        }
    }
    if(flag) return 1;

    int res = 0;
    for(int v = 0; v < n; v++){
        if( !G[u][v] ) continue;
        if( !visited2[v]){
            visited2[v] = true;
            res += dfs(v, visited2);
            visited2[v] = false;
        }
    }
    visited2[u] = true;
    return res;
}

int main(){
    cin>>n>>m;
    for(int i=0;i < m; i++){
        int a, b;
        cin>>a>>b;
        a--;b--;
        G[a][b] = G[b][a] = true;
    }

    visited[0] = true;
    int ans = dfs(0,visited);
    cout<< ans <<endl;
    
}

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

int binarysearch(int a[], int n, int item)
{
	int high=n-1, low=0, mid;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(a[mid]==item) return 1;
		else if(a[mid]<item) low=mid+1;
		else high=mid-1;
	}
	return 0;
	
}

int main()
{
	int a[3][3], n, i, j, count;
	for(i=0; i<3; i++)
	{
		for(j=0; j<3; j++)
		{
			scanf("%d", &a[i][j]);
		}
	}
	scanf("%d", &n);
	int arr[n];
	for(i=0; i<n; i++)
	{
		scanf("%d", &arr[i]);
	}
	
	sort(arr, arr+n);
	
	/*count=0;
	while(i<3 || j<3)
	{
		if(binarysearch(arr, n, a[i][j]))
		{
			count++;
			i++;
			if(count==3)
			{
				printf("Yes");
				return 0;
			}
		}
		else
		{
			count=0;
			i=0;
			j++;
			continue;
		}
		i=0;
		j=0;
		if(binarysearch(arr, n, a[i][j]))
		{
			count++;
			j++;
			if(count==3)
			{
				printf("Yes");
				return 0;
			}
		}
		else
		{
			count=0;
			j=0;
			i++;
			continue;
		}
		
	}
	
	count=0;
	while(i<3 && j<3)
	{
		if(binarysearch(arr, n, a[i][j]))
		{
			i++;
			j++;
			count++;
		}
		else break;
	}
	if(count==3)
	{
		printf("Yes");
		return 0;
	}
	count=0;
	for(i=0; i<3; i++)
	{
		for(j=0; j<3; j++)
		{
			if(i+j==2 && binarysearch(arr, n, a[i][j])) count++;
		}
	}
	if(count==3)
	{
		printf("Yes");
		return 0;
	}
	printf("No");
	return 0;
	*/
	
	if(binarysearch(arr, n, a[0][0]) && binarysearch(arr, n, a[0][1]) && binarysearch(arr, n, a[0][2])) printf("Yes");
	else if(binarysearch(arr, n, a[1][0]) && binarysearch(arr, n, a[1][1]) && binarysearch(arr, n, a[1][2])) printf("Yes");
	else if(binarysearch(arr, n, a[2][0]) && binarysearch(arr, n, a[2][1]) && binarysearch(arr, n, a[2][2])) printf("Yes");
	else if(binarysearch(arr, n, a[0][0]) && binarysearch(arr, n, a[1][0]) && binarysearch(arr, n, a[2][0])) printf("Yes");
	else if(binarysearch(arr, n, a[0][1]) && binarysearch(arr, n, a[1][1]) && binarysearch(arr, n, a[2][1])) printf("Yes");
	else if(binarysearch(arr, n, a[0][2]) && binarysearch(arr, n, a[1][2]) && binarysearch(arr, n, a[2][2])) printf("Yes");
	else if(binarysearch(arr, n, a[0][0]) && binarysearch(arr, n, a[1][1]) && binarysearch(arr, n, a[2][2])) printf("Yes");
	else if(binarysearch(arr, n, a[2][0]) && binarysearch(arr, n, a[1][1]) && binarysearch(arr, n, a[0][2])) printf("Yes");
	else printf("No");
	return 0;
}


Measured memory_bytes: 256
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>

using namespace std;

#define f first
#define s second
#define pb push_back
#define pp pop_back
#define mp make_pair
#define ll long long
#define ld double
#define ull unsigned long long
#define PI pair < int, int > 

const int N = 1e5 + 123;
const int M = 123;
const ld Pi = acos(-1);
const ll Inf = 1e18;
const int inf = 1e9;
const int mod = 1e9 + 7;
const int Sz = 501;
const int MOD = 1e9 + 7;

void add(int &a, int b) {
  a += b;
  if (a >= mod) a -= mod;
}
int mult(int a, int b) {
  return 1ll * a * b % mod;
}
int sum(int a, int b) {
  add(a, b);
  return a;
}

int n, k, a[N];
ll s[N], p[N], S[N];

void solve() { 
  cin >> n >> k;
  for (int i = 1;i <= n;i++) {
    cin >> a[i];
    p[i] = p[i - 1] + max(0, a[i]);
    S[i] = S[i - 1] + a[i];
  }
  for (int i = n;i;i--) {
    s[i] = s[i + 1] + max(0, a[i]);
  }
  ll ans = -1e18;
  for (int i = 1;i + k - 1 <= n;i++) {
    ll now = p[i - 1] + s[i + k] + max(0ll, S[i + k - 1] - S[i - 1]);
    ans = max(ans, now);
  }
  cout << ans << endl;
}
  
int main() {
  #ifdef wws
   freopen("in", "r", stdin);
   // freopen("in", "w", stdout);
  #endif 
  ios_base::sync_with_stdio(0);
  int tt = 1; 
  while(tt--) solve();
  return 0;
}

Measured memory_bytes: 2944
class Card:
    def __init__(self, info):
        self.suit = info[0]
        self.number = info[1]
    
    def getSuit(self):
        return self.suit
    
    def getNumber(self):
        return self.number
    
    def __repr__(self):
        return self.suit + str(self.number)
    
def isSameCard(card1, card2):
    return card1.getNumber() == card2.getNumber() and card1.getSuit() == card2.getSuit()

def bubbleSort(Ain, N):
    for i in range(0,N):
        for j in range(N-1, i, -1):
            if Ain[j].getNumber() < Ain[j-1].getNumber():
                temp = Ain[j]
                Ain[j] = Ain[j-1]
                Ain[j-1] = temp

def selectionSort(Ain, N):
    for i in range(0,N):    # iは最小のカードが入る場所
        minj = i
        for j in range(i+1,N):   # jは最小候補カードのインデックス
            if Ain[j].getNumber() < Ain[minj].getNumber():
                minj = j
        temp = Ain[i]
        Ain[i] = Ain[minj]
        Ain[minj] = temp

def printCards(Ain, N):
    for i in range(N-1):
        print(str(Ain[i]) + " ", end="")
    print(str(Ain[N-1]))

N = int(input())
Ain = [Card(info) for info in input().split()]
Ab = [i for i in Ain]
As = [i for i in Ain]
bubbleSort(Ab, N)
selectionSort(As, N)
printCards(Ab, N)
print("Stable")
printCards(As, N)
for i in range(0,N):
    if not isSameCard(Ab[i], As[i]):
        print("Not stable")
        break
    elif i != N-1:
        continue
    print("Stable")



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

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

    if (c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o')
    {
        cout << "vowel" << endl;
    }
    else
    {
        cout << "consonant" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
from collections import Counter
a = input()
a_list = list(map(int, input().split()))
ans = 0
b_list = []
c_list = []

for i in a_list:
    b_list.append(i+1)
    c_list.append(i-1)

ans_list = a_list + b_list + c_list
counter = Counter(ans_list)
print(counter.most_common()[0][1])

Measured memory_bytes: 33348
N = int(input())
B_list = list(map(int, input().split()))

A_list = []
for i, B in enumerate(B_list):
    if not A_list:
        if len(B_list) > 1 and B > B_list[i+1]:
            A_list.append(B)
            A_list.append(B_list[i+1])
        else:
            A_list.append(B)
            A_list.append(B)
    elif i < len(B_list)-1:
        if B > B_list[i+1]:
            A_list.append(B_list[i+1])
        else:
            A_list.append(B)
    else:
        A_list.append(B)
print(sum(A_list))

Measured memory_bytes: 3064
A, B, C = map(int, input().split())
ans = 0

while 1:
    if A%2 != 0 or B%2 != 0 or C%2 != 0:
        print(ans)
        break
    else:
        tmp = [B//2 + C//2, C//2 + A//2, A//2 + B//2]
        if tmp == [A,B,C]:
            print(-1)
            break
        else:
            A,B,C = tmp[0], tmp[1], tmp[2]
            ans += 1

Measured memory_bytes: 3064
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	s = input()
	n = len(s)
	m = n // 2
	ct = 0
	for i in range(m):
		if s[i] != s[n - i - 1]:
			ct += 1
	print(ct)

if __name__=='__main__':
	main()


Measured memory_bytes: 5400
def main():
  MOD =  10**9 + 7
  N, K = map(int, input().split())
  ki = [[] for _ in range(N)]
  for i in range(N-1):
    a, b = map(int, input().split())
    ki[a-1].append(b-1)
    ki[b-1].append(a-1)
  d = [-1] * N
  que = []
  ans = K
  d[0] = 1
  for i, nex in enumerate(ki[0]):
    d[nex] = 1
    ans *= (K-i-1)
    ans %= MOD
    que.append(nex)
  while len(que) > 0:
    now = que.pop(0)
    count = 2
    for nex in ki[now]:
      if d[nex] != -1:
        continue
      d[nex] = 1
      ans *= (K-count)
      count += 1
      ans %= MOD
      que.append(nex)
  print(ans)
  
if __name__ == "__main__":
  main()
  

Measured memory_bytes: 23664
def yumiri(L, n):
  for i in range(len(L)):
    if L[i] > n:
      return i - 1

def naobou(d, q):
  newans = ans

  rd = t[d - 1] - 1
  rq = yumiri(ZL[rd], d)
  newans += SUMD[ZL[rd][rq] - ZL[rd][rq - 1] - 1] * c[rd]
  newans += SUMD[ZL[rd][rq + 1] - ZL[rd][rq] - 1] * c[rd]
  newans -= SUMD[ZL[rd][rq + 1] - ZL[rd][rq - 1] - 1] * c[rd] 
  del ZL[rd][rq]

  nd = q - 1
  nq = yumiri(ZL[nd], d)
  newans += SUMD[ZL[nd][nq + 1] - ZL[nd][nq] - 1] * c[nd]
  newans -= SUMD[d - ZL[nd][nq] - 1] * c[nd]
  newans -= SUMD[ZL[nd][nq + 1] - d - 1] * c[nd]
  ZL[nd].insert(nq + 1, d)

  newans -= s[d - 1][rd]
  newans += s[d - 1][nd]

  if newans < ans:
    ZL[rd].insert(rq, d)
    del ZL[nd][nq + 1]
    return ans
  else:
    t[d - 1] = q
    return newans 

def rieshon():
  ans = 0
  for i in range(D):
    ans += s[i][t[i] - 1]
    for j in range(26):
      if t[i] - 1 == j:
        L[j] = 0
        ZL[j].append(i + 1)
      else:
        L[j] += 1
        ans -= L[j] * c[j]
  for i in range(26):
    ZL[i].append(D + 1)
  return ans

import time
import random
startTime = time.time()

D = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(D)]

L = [0] * 26
ZL = [[0] for _ in range(26)]
SUMD = [0] * (D + 1)
for i in range(1, D + 1):
  SUMD[i] = SUMD[i - 1] + i

t = [0] * D
for i in range(D):
  ma = s[i][0]
  man = 0
  for j in range(1, 26):
    if s[i][j] == ma:
      if c[j] < c[man]:
        ma = s[i][j]
        man = j
    elif s[i][j] > ma:
      ma = s[i][j]
      man = j
  t[i] = man + 1

ans = rieshon()
while time.time() - startTime < 1.95:
  d = random.randrange(D) + 1
  q = random.randrange(26) + 1
  if t[d - 1] == q: continue
  ans = naobou(d, q)

for i in range(D):
  print(t[i])


Measured memory_bytes: 9724
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include <cmath>

using namespace std;
const long long INF = (long long) (1e18)+1;

int main() {
  long long n, m;
  cin >> n >> m;
  vector<long long> nums(n);
  long long ans = 0;
  long long sum = 0;
  for(int i=0; i<n; i++) {
    cin >> nums[i];
    sum += nums[i];
  }
  // cout << "?" << endl;
  // int minmun = sum/(4*m);
  for(int i=0; i<n; i++) {
    if (nums[i]*(4*m) >= sum) ans++;
  }
  // cout << ans << endl;
  if (ans >= m) {
    cout << "Yes" << endl;  
  } else {
    cout << "No" << endl;
  }
  
  return 0;
  
}

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

#define fst first
#define snd second
#define mp make_pair
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n)-1;i>=(a);--i)
#define all(x) (x).begin(),(x).end()

template <typename T1, typename T2>
bool umin(T1 &x, const T2 &y) {return (x>y ? (x=y,true):false);}
template <typename T1, typename T2>
bool umax(T1 &x, const T2 &y) {return (x<y ? (x=y,true):false);}

template <typename T>
void read(T& x) {
    char ch;
    T p = 1; x = 0;
    do {ch = getchar();} while(ch <= ' ');
    if (ch == '-') p = -1, ch = getchar();
    while (ch>='0' && ch<='9') x = x*10 + ch-'0', ch = getchar();
    x *= p;
}

void read(string& x) {
    char ch;
    do {ch = getchar();} while (ch <= ' ');
    while (ch > ' ') x += ch, ch = getchar();
}

void read(char& x) {do {x = getchar();} while (x <= ' ');}
template<typename T, typename... R>
void read(T& x, R&... y) { read(x); read(y...); }

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pii;

const int N = (int)2e5+3;
const int INF = (int)1e9+17;
const ll mod = (ll)1e9+7;
const ll LLINF = (ll)1e18+17;
const ld pi = (ld)acos(-1.0);


int n;
string s[N];


int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    read(n);
    rep(i, 0, n) read(s[i]);
    string handle;
    read(handle);
    int Less = 0;
    int Greater = 0;
    int All = 0;
    rep(i, 0, n) {
        string user = s[i];
        replace(all(user), '?', 'a');
        bool isLess = user <= handle;
        user = s[i];
        replace(all(user), '?', 'z');
        bool isGreater = user >= handle;
        if (isLess && isGreater) {
            ++All;
        } else Less += isLess, Greater += isGreater;
    }
    rep(i, Less, Less+All+1) printf("%d%c", i+1, " \n"[i==Less+All]);

    return 0;
}


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

int main(){
  int N; cin >> N;
  vector<double> As(N);
  double sum = 0;
  for(int i = 0; i < N; i++){
    double a;
    cin >> a;
    sum += 1 / a;
  }
  
  printf("%lf",  1 / sum );
  return 0;
}


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

int Pow(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) {
			res *= a;
		}
		a *= a;
		b >>= 1;
	}
	return res;
}

int main()
{
	cout << fixed << setprecision(8) << endl;
	int n, m, k;
	while (cin >> n >> m >> k, n | m | k) {
		vector<vector<int>> dp(n + 1, vector<int>(n * m + 1));
		dp[0][0] = 1;
		for (int i = 1; i <= n; i++) {
			for (int j = i - 1; j <= m * (i - 1); j++) {
				for (int k = 1; k <= m; k++) {
					dp[i][j + k] += dp[i - 1][j];
				}
			}
		}
		ld res = 0;
		for (int i = 0; i <= n * m; i++) {
			res += dp[n][i] * max(1, i - k) / (ld)Pow(m, n);
		}
		cout << res << endl;
	}
	return 0;
}

Measured memory_bytes: 3356
package main

import (
	"fmt"
)

// 選択ソート
func main() {

	var num int
	// fmt.Scanは自動で空白区切で読み込む
	fmt.Scan(&num)
	nums := make([]int, num)
	for i := range nums {
		fmt.Scan(&nums[i])
	}

	selectSort(nums)
}

func selectSort(nums []int) {
	var count int
	for i := 0; i < len(nums); i++ {
		min := nums[i]
		minPosition := i
		for j := i; j < len(nums); j++ {
			if min > nums[j] {
				min = nums[j]
				minPosition = j
			}
		}
		if i != minPosition {
			tmp := nums[i]
			nums[i] = nums[minPosition]
			nums[minPosition] = tmp
			count++
		}
	}
	output(nums, count)
}

func output(nums []int, count int) {
	for k := 0; k < len(nums); k++ {
		if k != len(nums)-1 {
			fmt.Print(nums[k], " ")
		} else {
			fmt.Println(nums[k])
		}
	}
	fmt.Println(count)
}



Measured memory_bytes: 1132
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define put(i) cout<<fixed<<i<<endl
using namespace std;
using ll = long long;

int main(){
    ll x, i; cin >> x;
    ll a = 100;
    for(i = 0; a < x; i++){
        a *= 1.01;
    }
    put(i);
}

Measured memory_bytes: 3636
#include<iostream>
using namespace std;
long long N, A[87], CurrentMoney=1000;
int main() {
	cin>>N;
	for(int i=1; i<=N; i++) cin>>A[i];
	for(int i=1; i<=N-1; i++) {
		long long Stocks=0;
		if(A[i]<A[i+1]) Stocks=CurrentMoney/A[i];
		CurrentMoney+=(A[i+1]-A[i])*Stocks;
	}
	cout<<CurrentMoney<<endl;
}

Measured memory_bytes: 3560
#include <iostream>
#include <string>
using namespace std;
int main(void){
    string s;
    int a[3]={};
    cin>>s;
    for(int i=0;i<3;i++){
        switch(s[i]){
            case 'a':
                a[0]=1;
                break;
            case 'b':
                a[1]=1;
                break;
            case 'c':
                a[2]=1;
                break;
        }
    }
    if(a[0]+a[1]+a[2]==3){
        cout<<"Yes";
    } else {
        cout<<"No";
    }
    return 0;
}


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

using namespace std;

int main() {
	Int X;
	cin >> X;

	int ans = 0;
	Int sum = 100;
	while (sum < X) {
		sum = sum + sum / 100;
		++ans;
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 3548
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
#define rep(i, n) for(ll i = 0;i < n;i++)
#define all(i) i.begin(), i.end()
template<class T, class U> bool cmax(T& a, U b) { if (a<b) {a = b; return true;} else return false; }
template<class T, class U> bool cmin(T& a, U b) { if (a>b) {a = b; return true;} else return false; }

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

  ll h, w;
  cin >> h >> w;
  vector<vl> a(h, vl(w));
  vector<vl> b(h, vl(w));

  rep(i, h) {
    rep(j, w) {
      cin >> a[i][j];
    }
  }
  rep(i, h) {
    rep(j, w) {
      cin >> b[i][j];
    }
  }

  vector<vl> c(h, vl(w));
  rep(i, h) {
    rep(j, w) {
      c[i][j] = a[i][j]-b[i][j];
      //cerr << c[i][j] << " ";
    }
    //cerr << endl;
  }

  //( h+ w) * max(ai) * 2 * 2(+-)
  ll ma = (80+80)*80*2 *2;
  ll ze = ma/2;
  ma *= 2;
  ma += 1000;

  vector<vector<vector<bool>>> dp(h, vector<vector<bool>>(w, vector<bool>(ma)));
  dp[0][0][c[0][0]+ze] = true;

  rep(i, h) {
    rep(j, w) {
      for (ll k = -ze; k <= ze; k++) {
        if (i-1 >= 0 && k+c[i][j]+ze >= 0) {
          if (dp[i-1][j][k+c[i][j]+ze])
            dp[i][j][k+ze] = 1;
        }
        if (i-1 >= 0 && k-c[i][j]+ze >= 0) {
          if (dp[i-1][j][k-c[i][j]+ze])
            dp[i][j][k+ze] = 1;
        }
        if (j-1 >= 0 && k+c[i][j]+ze >= 0) {
          if (dp[i][j-1][k+c[i][j]+ze])
            dp[i][j][k+ze] = 1;
        }
        if (j-1 >= 0 && k-c[i][j]+ze >= 0) {
          if (dp[i][j-1][k-c[i][j]+ze])
            dp[i][j][k+ze] = 1;
        }
      }
    }
  }

  ll ans = 1e20;
  for (ll k = -ze; k <= ze; k++) {
    if (dp[h-1][w-1][k+ze]) {
      cmin(ans, abs(k));
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 84608
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define temT template<typename T>
using namespace std;
typedef long long ll;
const ll mo=998244353;
const int N=int(2e5)+10;

int n,K,a[11][2];

temT inline T add(T x,T y){ return (x+=y,x>=mo)?x-=mo:x; }
temT inline T dec(T x,T y){ return (x-=y,x<0)?x+=mo:x; }
temT inline T mul(T x,T y){ return T((ll)x*y%mo); }

#define RT 1,1,n
#define LS p<<1,l,mid
#define RS p<<1|1,mid+1,r
int sum[N*4],tag[N*4];
void mt(int p){ sum[p]=add(sum[p<<1],sum[p<<1|1]); }
void fill(int p,int l,int r,int v){
	sum[p]=add(sum[p],mul(r-l+1,v));
	tag[p]=add(tag[p],v);
}
void pd(int p,int l,int r){
	int mid=(l+r)>>1;
	fill(LS,tag[p]); fill(RS,tag[p]);
	tag[p]=0;
}
void upd(int p,int l,int r,int el,int er,int v){
	if(el<=l && r<=er) return fill(p,l,r,v),void();
	pd(p,l,r); int mid=(l+r)>>1;
	if(el<=mid)		upd(LS,el,er,v);
	if(er>=mid+1)	upd(RS,el,er,v);
	mt(p);
}
int ask(int p,int l,int r,int ep){
	if(l==r) return sum[p];
	pd(p,l,r); int mid=(l+r)>>1;
	if(ep<=mid)		return ask(LS,ep);
	if(ep>=mid+1)	return ask(RS,ep);
}

int main(){
	cin>>n>>K;
	FOR(i,1,K) cin>>a[i][0]>>a[i][1];
	upd(RT,1,1,1);
	FOR(i,1,n-1){
		int x=ask(RT,i);
		FOR(j,1,K){
			int l=i+a[j][0],r=i+a[j][1];
			if(l>n) continue; l=min(l,n),r=min(r,n);
			upd(RT,l,r,x);
		}
	}
	cout<<ask(RT,n);
	return 0;
}

Measured memory_bytes: 7728
H,W,K=gets.split.map(&:to_i)

MOD=10**9+7

dp=Array.new(H+1){Array.new(W,0)}
dp[0][0]=1

oks=[]
[0,1].repeated_permutation(W-1).each do |f|
    valid_flag=true
    f.each_cons(2) do |i,j|
        valid_flag=false if i==1 && j==1
    end
    add=Array.new(W,0)
    W.times do |w|
        add[w]=1 if w<W-1 && f[w]==1
        add[w]=-1 if w>0 && f[w-1]==1
    end
    oks << add if valid_flag
end

H.times do |h|
    dph=dp[h]
    dph1=dp[h+1]
    oks.each do |add|
        W.times do |w|
            ww=w+add[w]
            dph1[ww]+=dph[w]
            dph1[ww]-=MOD if dph1[ww]>=MOD
        end
    end
end
p dp[H][K-1]

Measured memory_bytes: 1788
#include<stdio.h>
int main() {
  int data[5], sum = 0, ave, i;
  for(i = 0; i < 5; i++) {
    scanf("%d", &data[i]);
    if(data[i] < 40) {
      data[i] = 40;
    }
    sum += data[i];
  }
  ave = sum / 5;
  printf("%d\n", ave);
  return 0;
}

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

int main() {
  double a,b,h,m,t=0;
  cin>>a>>b>>h>>m;
  double doh,dom=0;
  
  t=h*60+m;
  doh=t*0.5;
  dom=m*6;
  
  cout<<fixed<<setprecision(15)<<sqrt(a*a+b*b-2*a*b*cos(M_PI*(doh-dom)/180));
}

Measured memory_bytes: 4244
#include <algorithm>
#include <bitset>
#include <cmath>
#include <complex>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <vector>

const int MOD = 1e9 + 7;
const int iINF = 2147483647 / 2;
const long long int llINF = 9223372036854775807 / 2;

using namespace std;
using ll = long long int;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vvvl = vector<vector<vector<ll>>>;

typedef pair<ll, ll> pll;
bool paircomp(const pll &a, const pll &b) {
  if (a.first == b.first)
    return a.second < b.second;
  return a.first < b.first;
}

#define REP(i, n) for (ll i = 0; i < (n); i++)
#define RREP(i, n) for (ll i = (n)-1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define AUTO(i, m) for (auto &i : m)
#define ALL(a) (a).begin(), (a).end()
#define MAX(vec) *std::max_element(vec.begin(), vec.end())
#define MIN(vec) *std::min_element(vec.begin(), vec.end())
#define ARGMAX(vec)                                                            \
  std::distance(vec.begin(), std::max_element(vec.begin(), vec.end()))
#define ARGMIN(vec)                                                            \
  std::distance(vec.begin(), std::min_element(vec.begin(), vec.end()))
#define REV(T) greater<T>()
#define PQ(T) priority_queue<T, vector<T>, greater<T>>
#define VVL(a, b, c) vector<vector<ll>>(a, vector<ll>(b, c))
#define VVVL(a, b, c, d)                                                       \
  vector<vector<vector<ll>>>(a, vector<vector<ll>>(b, vector<ll>(c, d)))
#define SP(a) setprecision(a)
#define SQRT(a) sqrt((long double)(a))
#define DPOW(a, b) pow((long double)(a), (long double)(b))
#define UNIQUE(vec)                                                            \
  do {                                                                         \
    sort(ALL((vec)));                                                          \
    (vec).erase(std::unique(ALL((vec))), (vec).end());                         \
  } while (0)

ll POW(ll n, ll m) {
  if (m == 0) {
    return 1;
  } else if (m % 2 == 0) {
    ll tmp = POW(n, m / 2);
    return (tmp * tmp);
  } else {
    return (n * POW(n, m - 1));
  }
}

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll N;
  cin >> N;
  vl A(N);
  vector<bool> used(N, false);
  ll B = 0;
  REP(i, N) {
    cin >> A[i];
    B = B ^ A[i];
  }
  ll ans = 0;
  RREP(i, 40) {
    if ((B >> i) % 2 == 0)
      continue;
    bool ok = false;
    REP(j, N) {
      if (used[j])
        continue;
      if ((A[j] >> i) % 2 == 1 && (A[j] % (1LL << i)) == 0) {
        used[j] = true;
        ok = true;
        B = B ^ ((1LL << (i + 1LL)) - 1LL);
        // cout << B << "," << i << endl;
        ans++;
        break;
      }
    }
    if (!ok) {
      cout << -1 << endl;
      return 0;
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define MAXN 300005
#define LL long long
#define len(p) (n[p].r - n[p].l + 1)
using namespace std;

int N,M;
struct Node{
	int l,r;
	Node(int l=0, int r=0):l(l), r(r){}
	
	bool operator < (const Node& n1) const{
		return r-l < n1.r-n1.l;
	}
} n[MAXN];

//
int fw[MAXN];
int lbt(int x){
	return x & (-x);
}

int getsum(int x){
	int ans = 0;
	for(;x;x -= lbt(x)){
		ans += fw[x];
	}
	return ans;
}

void change(int x, int dv){
	for(;x<=M;x += lbt(x)){
		fw[x] += dv;
	}
}
//


int main(){
	ios::sync_with_stdio(0);
	
	cin>>N>>M;
	for(int i=1;i<=N;i++){
		cin>>n[i].l>>n[i].r;
	}
	
	sort(n+1, n+1+N);
	
	int p = 0;
	for(int d=1;d<=M;d++){
		while(p+1<=N && len(p+1)<d){
			p++;
			change(n[p].l, +1);
			change(n[p].r+1, -1);
		}
		
		int ans = 0;
		for(int j=d;j<=M;j+=d){
			ans += getsum(j);
		}
		cout<<ans + (N-p)<<endl;
	}
	
	
	return 0;
}

Measured memory_bytes: 3712
<?php
fscanf(STDIN, "%d %d", $N, $M);

// 
$ans = max(0, pow(10, $N - 1));
if($N - 1 == 0) {
	$ans = 0;
}
$ans = "{$ans}";

$map = [];

for($i = 0; $i < $M; $i++) {
	fscanf(STDIN, "%d %d", $s, $c);
	// 左から数えて１つめが０はNG
	if($N > 1 && $s == 1 && $c == 0) {
		echo "-1\n";
		exit;
	}
	
	// 同じ桁数目に違う値はNG
	if(array_key_exists($s, $map) !== false && $map[$s] != $c) {
		echo "-1\n";
		exit;
	}
	$map[$s] = $c;
	
	$ans[$s - 1] = $c;
}

echo "{$ans}\n";


Measured memory_bytes: 4604
#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>;
using Graph = vector<vector<int>>;

// header area

int main(){
    string S, T; cin >> S;
    cin >> T;

    if(S == T.substr(0, (int)S.size())) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3628
# -*- coding:utf-8 -*-

def solve():
    N, X = list(map(int, input().split()))
    L = list(map(int, input().split()))

    ans = 1
    d = 0

    for i in range(0, N):
        d = d + L[i]
        if not d <= X: break
        ans += 1
    
    print(ans)


if __name__ == "__main__":
    solve()


Measured memory_bytes: 3060
#include<iostream>
#include<algorithm>
using namespace std;
int a[55];
int plate[55];
int main()
{
    int n, k, r, res = 0;
    int i, j;
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i++)
        scanf("%d", a + i);
    r = min(n, k);
    for(int A = 0; A <= r; A++)
    {
        for(int B = 0; A+B <= r; B++)
        {
            for(i = 0; i < A; i++)
                plate[i] = a[i];
            for(j = 0; j < B; j++)
                plate[i+j] = a[n-1-j];
            sort(plate, plate+A+B);
            i = 0;
            while(i < k-A-B && plate[i] < 0)
            {
                i++;
            }
            int sum = 0;
            for(; i < A+B; i++)
                sum += plate[i];
            res = max(res, sum);
        }
    }
    printf("%d\n", res);
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(ll i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  ll r, c, k;
  cin >> r >> c >> k;
  vector<vi> g(r + 3, vi(c + 3, 0));
  rep(i, k) {
    ll a, b, v;
    cin >> a >> b >> v;
    a--, b--;
    g[a][b] = v;
  }
  vector<vector<vl>> dp(r + 3, vector<vl>(c + 3, vl(5, -1e16)));
  rep(i, r) rep(j, c) rep(m, 4) dp[i][j][m] = -1e16;
  dp[0][0][0] = 0;
  rep(w, r + c + 1) rep(i, r) rep(m, 4) {
    ll j = w - i;
    if(j < 0 || c < j) continue;
    if(dp[i][j][m] == -1e16) continue;
    // printf("dp[%d][%d][%d]=%d\n", i, j, m, dp[i][j][m]);
    dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j][m]);
    dp[i][j + 1][m] = max(dp[i][j + 1][m], dp[i][j][m]);
    if(m < 3) {
      dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j][m] + g[i][j]);
      dp[i][j + 1][m + 1] = max(dp[i][j + 1][m + 1], dp[i][j][m] + g[i][j]);
    }
  }
  ll ans = -1e16;
  rep(i, 2) rep(j, 2) rep(m, 4) ans = max(ans, dp[r - 1 + i][c - 1 + j][m]);
  cout << ans << endl;
}

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

int main() {
	string S;
	long long N;
	map<char, bool> mp;
	long long COUNT = 26;
	vector<string> VS = { "" };
	cin >> S;
	for (int i = S.size() - 1; i >= 0; i--) {
		if (!mp[S[i]]) COUNT--, mp[S[i]] = true;
		VS[VS.size() - 1] = S[i] + VS[VS.size() - 1];
		if (COUNT == 0) {
			VS.push_back("");
			mp.clear();
			COUNT = 26;
		}
	}
	reverse(VS.begin(), VS.end());
	string ANS = "";
	mp.clear();
	for (char C : VS[0]) mp[C] = true;
	for (char C = 'a'; C <= 'z'; C++) if (!mp[C]) {
		ANS = ANS + C;
		mp.clear();
		break;
	}
	for (int i = 1; i < VS.size(); i++) {
		bool check = false;
		for (char C : VS[i]) {
			if (check) {
				mp[C] = true;
			}
			else if (C == ANS[ANS.size() - 1]) check = true;
		}
		for (char C = 'a'; C <= 'z'; C++) if (!mp[C]) {
			ANS = ANS + C;
			mp.clear();
			break;
		}
	}
	cout << ANS << endl;
}

Measured memory_bytes: 1028
from sys import stdin
s=int(stdin.readline().rstrip())
al=[s]
while True:
    if al[-1]%2 == 0:
        new = int(al[-1]/2)
    else:
        new = int(3*al[-1]+1)
    if new in al:
        al.append(new)
        print(len(al))
        break
    al.append(new)

Measured memory_bytes: 3060
input_line = map(int,raw_input().split(" "))
a = input_line[0]
b = input_line[1]

if a != b:
	if a == 1:
		print "Alice"
	elif b == 1:
		print "Bob"
	elif a > b :
		print "Alice"
	elif a < b:
		print "Bob"
else:
	print "Draw"

Measured memory_bytes: 2692
use std::io::*;
use std::str::FromStr;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

const MOD: i64 = 1e+9 as i64 + 7;

fn main() {
    let s = read::<String>().chars().collect::<Vec<char>>();
    let n = s.len();
    let mut acnt = vec![0; n + 1];
    let mut ccnt = vec![0; n + 1];
    let mut qcnt = vec![0; n + 1];
    let mut threes = vec![1; n + 1];
    for i in 0..n {
        threes[i + 1] = threes[i] * 3 % MOD;
    }
    for i in 0..n {
        acnt[i + 1] += acnt[i];
        ccnt[i + 1] += ccnt[i];
        qcnt[i + 1] += qcnt[i];
        if s[i] == 'A' {
            acnt[i + 1] += 1;
        } else if s[i] == 'C' {
            ccnt[i + 1] += 1;
        } else if s[i] == '?' {
            qcnt[i + 1] += 1;
        }
    }
    let mut ans = 0;
    for i in 0..n {
        if s[i] != 'B' && s[i] != '?' {
            continue;
        }
        let lq = qcnt[i];
        let la = acnt[i];
        let mut l = la * threes[lq as usize] % MOD;
        if lq > 0 {
            l = (l + lq * threes[lq as usize - 1]) % MOD;
        }
        let rq = qcnt[n] - qcnt[i + 1];
        let rc = ccnt[n] - ccnt[i + 1];
        let mut r = rc * threes[rq as usize] % MOD;
        if rq > 0 {
            r = (r + rq * threes[rq as usize - 1]) % MOD;
        }
        ans = (ans + l * r) % MOD;
    }
    println!("{}", ans);
}


Measured memory_bytes: 8444
/*input
4 3
1 2
2 3
2 4
2 10
1 100
3 1
hooded_sweater   
*/

#include <bits/stdc++.h>
using namespace std;
#define fast_io() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#ifndef ONLINE_JUDGE
#define debug(...) cout << "debug: " << #__VA_ARGS__ " = "; _dbg(__VA_ARGS__);
#define debuga(arr, n) _dbga(arr, n, #arr)
#else
#define debug(...)
#define debuga(arr, n)
#endif
typedef long long int ll;
#define int ll
#define F first
#define S second
#define float double
const int inf = LLONG_MAX;
typedef double db;
typedef vector<int> vi;
typedef pair<int, int> pii;

const int mod = 1e9+7;
const int N = 1e6+1;

using namespace std;

vector<ll> adj[N], counter(N);
void bfs(int s) {
  queue<int> q;
  vector<bool> used(N);
  vector<int> d(N), p(N);

  q.push(s);
  used[s] = true;
  p[s] = -1;
  while (!q.empty())
  {
    int v = q.front();
    q.pop();
    for (int u : adj[v])
    {
      if (!used[u])
      {
        counter[u] += counter[v];
        used[u] = true;
        q.push(u);
        d[u] = d[v] + 1;
        p[u] = v;
      }
    }
  }
}

int32_t main() {
  fast_io();

  int n, q; cin >> n >> q;
  for (int i = 0; i < n-1; i++) {
    int u, v; cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  while (q--) {
    int p, x; 
    cin >> p >> x;
    counter[p] += x;
  }
  bfs(1);
  for (int i=1; i < n+1; i++) {
    cout << counter[i] << " ";
  }

  return 0;
}

Measured memory_bytes: 56704
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0117
AC
"""
import sys
from sys import stdin
input = stdin.readline


def warshallFloyd(V, dp):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dp[i][k] + dp[k][j] < dp[i][j]:
                    dp[i][j] = dp[i][k] + dp[k][j]


def main(args):
    n = int(input())
    m = int(input())
    dp = [[float('inf')]*(n) for _ in range(n)]
    for i in range(n):
        dp[i][i] = 0
    for _ in range(m):
        a, b, c, d = [int(x) for x in input().split(',')]
        dp[a-1][b-1] = c
        dp[b-1][a-1] = d
    s, g, V, P = [int(x) for x in input().split(',')]

    warshallFloyd(n, dp)

    print(V - dp[s-1][g-1] - dp[g-1][s-1] - P)


if __name__ == '__main__':
    main(sys.argv[1:])

Measured memory_bytes: 7880