akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

typedef pair<long long, long long> pi;

long long n, a, b, c, q, k, x, y, dist[100001], p[100001][20], depth[100001];
vector<pi> adj[100001];

void dfs(long long node){
        for(vector<pi>::iterator it = adj[node].begin(); it != adj[node].end(); it++){
                if(it->first == 1 || depth[it->first] != 0 || dist[it->first] != 0) continue;
                dist[it->first] = dist[node]+it->second;
                p[it->first][0] = node;
                depth[it->first] = depth[node]+1;
                dfs(it->first);
        }
}

long long lca(long long x, long long y){
        if(depth[x] < depth[y]) swap(x, y);
        for(int k = 19; k >= 0; k--){
                if(p[x][k] != -1 && depth[p[x][k]] >= depth[y]) x = p[x][k];
        }
        if(x == y) return x;
        for(int k = 19; k >= 0; k--){
                if(p[x][k] != p[y][k]){
                        x = p[x][k];
                        y = p[y][k];
                }
        }
        return p[x][0];
}

long long distance(long long x, long long y){
        return dist[x]+dist[y]-2*dist[lca(x, y)];
}

int main(){
        cin >> n;
        for(int i = 0; i < n-1; i++){
                cin >> a >> b >> c;
                adj[a].push_back(pi(b, c));
                adj[b].push_back(pi(a, c));
        }
        memset(p, -1, sizeof(p));
        depth[1] = 0;
        dfs(1);
        for(int k = 1; k < 20; k++){
                for(int i = 1; i <= n; i++){
                        if(p[i][k-1] != -1) p[i][k] = p[p[i][k-1]][k-1];
                }
        }
        cin >> q >> k;
        for(int i = 0; i < q; i++){
                cin >> x >> y;
                cout << distance(x, k)+distance(k, y) << "\n";
        }
}

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

int main(void)
{
  int value, num;
  int sum = 0, ave = 0, row = 0;
  char a;
  
  while(cin >> value >> a >> num)
    {
      sum += value * num;
      ave += num;
      row++;
    }
  cout << sum << endl << (int)(ave / (double)row + 0.5) << endl;
  return 0;
}

Measured memory_bytes: 0
N, A, B = map(int,input().split(" "))
S = input()
count = {"a":0,"b":0}
for s in S:
    if s == "a" and count["a"] + count["b"] < A+B:
        count["a"] += 1
        print("Yes")
    elif s == "b" and count["a"] + count["b"] < A+B and count["b"]<B:
        count["b"]+=1
        print("Yes")
    else:
        print("No")

Measured memory_bytes: 4016
#include<stdio.h>

int main(void)
{
	int N, p, i, max = 0, ans = 0;
	scanf("%d", &N);
	for (i = 0; i < N; ++i) {
		scanf("%d", &p);
		ans += p;
		if (max < p) {
			max = p;
		}
	}
	printf("%d", ans - max + max / 2);
	return 0;
}

Measured memory_bytes: 128
import math
A, B, N = map(int, input().split())
x = N // 2
def floor(t):
    return math.floor(t)
li = []
if B < N:
    print(floor((A*(B - 1)) / B) - A * floor((B - 1)/B))
elif B == N:
    print(floor((A*(N - 1)) / B) - A * floor((N - 1)/B))
else:
    print(floor((A*(N)) / B) - A * floor((N)/B))


Measured memory_bytes: 62220
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int H, W, K;
int S[12][1002]={0};

int sum(int r1, int c1, int r2, int c2){
	if(r1<1 || r2<r1 || r2>H) return 0;
	if(c1<1 || c2<c1 || c2>W) return 0;
	int ret = 0;
	for(int i=r1; i<=r2; i++){
		for(int j=c1; j<=c2; j++){
			ret += S[i][j];
		}
	}
	return ret;
};

int maxWpercell(int b, int c1, int c2){
	if(c1<1 || c2<c1 || c2>W) return 0;

	if(b==0){
		return sum(1, c1, H, c2);
	}

	vector<int> hv;
	for(int i=0, p=1; p<=b; p=p*2, i++){
		if((b&p)/p){ hv.push_back(i+1); }
	}

	int ret=0, v=0;
	int s=1, e=1;
	for(int i=0; i<hv.size() && s<=H; i++){
		e = hv[i];
		v = sum(s, c1, e, c2);
		if(v>ret){ ret = v; }
		s = e+1;
	}
	v = sum(s, c1, H, c2); //最後
	if(v>ret){ ret = v; }
	return ret;
}

int searchMaxR(int b, int c1){
	int s, e;
	int ret=0;

	if(maxWpercell(b, c1, W)<=K){
		return W;
	}
	if(maxWpercell(b, c1, c1)>K){
		return -1;
	}

	s=c1, e=W;
	while(s!=e && e<=W){
		int v = maxWpercell(b, c1, e);
		if(v>K){
			e = (s+e)/2;
		}
		else if(v==K){
			if(maxWpercell(b, c1, e+1)>K){
				break;
			}
			else{
				e++;
			}
		}
		else{ //v<K
			s = e;
			e = (s+W)/2;
		}
	}
	return e;
}

int main(int argc, char* argv[]){
	cin >> H >> W >> K;

	for(int i=0; i<12; i++){
		for(int j=0; j<1002; j++){
			S[i][j] = 0;
		}
	}

	for(int i=1; i<=H; i++){
		string str;
		cin >> str;
		for(int j=1; j<=W; j++){
			char c[2] = {0};
			c[0] = str[j-1];
			S[i][j] = atoi(c);
		}
	}

	//0で可能か確認
	if(sum(1, 1, H, W)<=K){
		printf("%d\n", 0);
		return 0;
	}

	int ans = INT_MAX;
	for(int b=0; b<(1<<H-1); ++b){ //H方向 bit search
		int tmpans = 0;
		for(int i=1, p=1; p<=b; p=p*2, i++) {
			if((b&p)/p){
				tmpans++;
			}
		}

		int s=1, e=W;
		int possible_for_b = 1;
		while(s<W && e<=W && s<=e){
			e = searchMaxR(b, s);
			if(e<=0){
				possible_for_b = 0;
				break;
			}
			if(e>=W){
				break;
			}
			else{ //e<W 割る
				tmpans++;
				s = e+1;
				e = W;
				continue;
			}
		}
		if(possible_for_b==0){ continue; }
		if(tmpans<ans){ ans = tmpans; }
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 256
f=0
while 1:
  a, b = map(int, raw_input().split())
  if a==b==0: break
  x=[i for i in range(a,b+1) if (i%4==0 and (i%100!=0 or i%400==0))]
  if x==[]: x=["NA"]

  if f: print
  for e in x: print e
  f=1

Measured memory_bytes: 4304
using System;
using System.Collections.Generic;
using System.Linq;

  struct input{
   public long D;
   public long N;
  }

class MainClass {
  static input input; 

  public static void Main (string[] args) {
    
    var temp = Console.ReadLine().Split(' ').Select(long.Parse);
    input.D = temp.ElementAt(0);
    input.N = temp.ElementAt(1);
   
    var ans = Math.Pow(100, input.D) * input.N;
    if(input.D == 0 && ans % 100 == 0){
      ans++;
    }else if(input.D == 1 && ans % 10000 == 0){
      ans += Math.Pow(100, input.D);
    }else if(input.D == 2 && ans % 1000000 == 0){
      ans += Math.Pow(100, input.D);
    }
    Console.WriteLine(ans);
  }
}

Measured memory_bytes: 13268
#include<cstdio>
#include<iostream>
using namespace std;
const int FULLS=1<<21;
const int mod=1e9+7;
const int N=22;
int n,a[N][N],dp[FULLS],S,num[FULLS];
inline void Add(int &x,int y){x+=y;x-=x>=mod? mod:0;}
inline int Count(int x){int sum=0;while(x){sum+=(x&1);x>>=1;}return sum;}
int main(){
	scanf("%d",&n);S=(1<<n);
	for(register int i=1;i<=n;i++)
		for(register int j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
	for(register int sta=0;sta<S;sta++)num[sta]=Count(sta);
	dp[0]=1;
	for(register int sta=0;sta<S;sta++)
		for(register int i=1;i<=n;i++)
			if(a[num[sta]+1][i]&&!((sta>>(i-1))&1))
				Add(dp[sta|(1<<(i-1))],dp[sta]);
	printf("%d\n",dp[S-1]);
	return 0;
}

Measured memory_bytes: 16768
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define MOD (int) (1e9+7)
#define INF (int) 2e9
#define LLINF (ll) 2e18

int main(){
    double n;
    cin >> n;
    double tmp =  ceil(n/1.08);
    if( floor(tmp*1.08)==n){
        cout << tmp << endl;
    } else{
        cout << ":(" << endl;
    }
    // printf("%d\n", N);
    return 0;
}

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

using namespace std;
typedef long long LL;
typedef pair<int,int> P;

int main(){
	int N, A;
	cin >> N >> A;
	if(N%500>A) cout << "No" << endl;
	else cout << "Yes" << endl;

	return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.List;
import java.util.ArrayList;
import java.lang.*;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] s = br.readLine().split(" ", 0);
        int n = Integer.parseInt(s[0]);
        int q = Integer.parseInt(s[1]);
        
        myList[] a = new myList[n];
        for (int i = 0; i < n; i++) {
            a[i] = new myList();
        }
        
        String l;
        String[] rem;
        char query;
        int t, x;
        for (int i = 0; i < q; i++) {
            l = br.readLine();
            query = l.charAt(0);
            rem = l.substring(2).split(" ", 0);
            t = Integer.parseInt(rem[0]);
            
            switch (query) {
                case '0':
                    x = Integer.parseInt(rem[1]);
                    a[t].pushBack(x);
                    break;
                case '1':
                    a[t].dump();
                    break;
                case '2':
                    a[t].clear();
                    break;
            }
        }
    }
}

class myList {
    List<Integer> list;
    
    myList() {
        list = new ArrayList<>();
    }
    
    void pushBack(int x) {
        list.add(x);
    }
    
    void dump() {
        int size = list.size();
        for (int i = 0; i < size; i++) {
            System.out.print(list.get(i));
            if (i != size - 1) {
                System.out.print(" ");
            }
        }
        System.out.println();
    }
    
    void clear() {
        list.clear();
    }
}
    



Measured memory_bytes: 127172
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int a,n;cin>>n;
  for(int i=1;i<=9;i++)
  {
    if(n%i==0)
    {
      int temp=n/i;
      if(temp>=1 && temp<=9) {cout<<"Yes"; return 0;}
    }
  }
  cout<<"No";
  return 0;
}

Measured memory_bytes: 256
# B - Bite Eating
# https://atcoder.jp/contests/abc131/tasks/abc131_b
"""
1~Nの数字がある
数列iの対応する値はL+i-1である

N = [1,2,3,4,5]
l = 1
対応する値=[2,3,4,5,6]

a = 対応する値の総和の絶対値を取得する
b = 1つだけ除外し、残った対応する値の総和の絶対値を取得する
aとbの差をなるべく小さくするには？
対応する値は負になることもある
"""

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

"""
L + i - 1の対応する値の配列を作成する 
"""
apple_taste = []
taste_total = 0
for i in range(1, n + 1):
    apple_taste.append(L + i - 1)
    taste_total += L + i - 1


"""
要素数が少ないので愚直に一つずつ除外していって差がより小さい箇所を探す
"""

abs_taste_total = abs(sum(apple_taste))
ans = 10 ** 9 # これを差の絶対値が少ないときに入れ替えるようにする
diff = 10 ** 9 # この子は差の絶対値を保持しておく

for i in apple_taste:
    current_total = taste_total - i # iを食べたときの合計値
    abs_current_total = abs(abs(taste_total) - abs(i)) # 現在の値の絶対値。マイナス同士で引くと右辺が正の数として扱われるので絶対値にする

    current_abs = abs(abs(abs_taste_total) - abs(current_total))
    if current_abs < diff:
        diff = current_abs
        ans = current_total

print(ans)


Measured memory_bytes: 3064
# from bisect import bisect_left

n = int(input())
s = input()
RL = []
GL = []
BL = []
for i in range(1, n + 1):
    word = s[i - 1]
    if word == "R":
        RL.append(i)
    elif word == "G":
        GL.append(i)
    else:
        BL.append(i)
nagasa_r = len(RL)
nagasa_g = len(GL)
nagasa_b = len(BL)
SBL = set(BL)
ans = 0
if nagasa_b == 0 or nagasa_g == 0 or nagasa_r == 0:
    ans = 0
else:
    out_count = 0
    for r in RL:
        for g in GL:
            bigger = max(r, g)
            smaller = min(r, g)
            delta = bigger - smaller
            if (r + g) % 2 == 0:
                outnumber = [bigger + delta, smaller - delta, (r + g) // 2]
            else:
                outnumber = [bigger + delta, smaller - delta]
            for num in outnumber:
                if num in SBL:
                    out_count += 1
            ans += nagasa_b
    ans -= out_count
print(ans)


Measured memory_bytes: 9256
#include <iostream>
#include <string>

int main(){
  int n;
  std::string s;

  std::cin >> n >> s;

  int ret = 1;
  for(int i = 0; i < n-1; i++){
    if(s[i] != s[i+1]) ret++;
  }

  std::cout << ret << std::endl;

  return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int main() {
    int n;
    string s;
    cin >> n >> s;
    char prev = ' ';
    int count = 0;
    for(auto c : s){
        if(c != prev){
            count++;
        }
        prev = c;
    }
    cout << count << endl;
	return 0;
}

Measured memory_bytes: 512
S = int(input())

dp = [0] * (S+1)

def rec(n):
    if dp[n] > 0:
        return dp[n]
    if n < 3:
        return dp[n]

    result = 1
    for i in range(n-3, 0, -1):
        result += rec(i)
    result %= 10 ** 9 + 7
    dp[n] = result
    return result

print(rec(S))


Measured memory_bytes: 68532
package main

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

var (
	readString func() string
	stdout     *bufio.Writer
)

func init() {
	readString = newReadString(os.Stdin)
	stdout = bufio.NewWriter(os.Stdout)
}

func newReadString(ior io.Reader) func() string {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	return func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
}

func readInt() int {
	return int(readInt64())
}

func readInt64() int64 {
	i, err := strconv.ParseInt(readString(), 0, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readIntSlice(n int) []int {
	b := make([]int, n)
	for i := 0; i < n; i++ {
		b[i] = readInt()
	}
	return b
}

func readLengthAndSlice() (int, []int) {
	n := readInt()
	return n, readIntSlice(n)
}

func printf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(stdout, f, args...)
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdout, args...)
}

func eprintln(args ...interface{}) (int, error) {
	return fmt.Fprintln(os.Stderr, args...)
}

// readString() string
// readInt() int
// readIntSlice(n int) []int
// readLengthAndSlice() []int

// -----------------------------------------------------------------------------

func main() {
	defer stdout.Flush()
	n := readInt()
	m := readInt()
	from1 := make(map[int]bool)
	fromN := make(map[int]bool)
	for i := 0; i < m; i++ {
		a := readInt()
		b := readInt()
		if a == 1 {
			from1[b] = true
		} else if a == n {
			fromN[b] = true
		}
		if b == 1 {
			from1[a] = true
		} else if b == n {
			fromN[a] = true
		}
	}

	for v := range from1 {
		if fromN[v] {
			println("POSSIBLE")
			return
		}
	}
	println("IMPOSSIBLE")
}

// -----------------------------------------------------------------------------


Measured memory_bytes: 8320
tate,yoko=map(int,input().split())
#ト字型に折る
def byodo(H,W):
    bigH=H//2+H%2
    smallH=H-bigH
    todif=10**10
    for i in range(W//2+1):
        Smin=min(H*i,smallH*(W-i))
        Smax=max(H*i,bigH*(W-i))
        todif=min(todif,Smax-Smin)
    for i in range(W//2+1,W):
        Smax=H*i
        Smin=smallH*(W-i)
        todif=min(todif,Smax-Smin)
    return(todif)
def france(H,W):#III
    if W%3:
        return(H)
    else:return(0)
print(min(byodo(tate,yoko),byodo(yoko,tate),france(yoko,tate),france(tate,yoko)))

Measured memory_bytes: 39408
// Author: Vamsi Krishna Reddy Satti
// With love for Competitive Programming!
 
#include <bits/stdc++.h>
using namespace std;
 
#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define cout_precision cout.setf(ios::fixed); cout.precision(32);
 
using ll = int64_t; using vll = vector<ll>; using vvll = vector<vll>;
using pll = pair<ll, ll>; using vpll = vector<pll>; using vvpll = vector<vpll>;
 
// ------------------------------------------------------------------------------------------------

ll n, ans;
string s;
map<string, ll> m;

void func() {
    cin >> n;
    for (ll i = 0; i < n; i++) {
        cin >> s;
        sort(s.begin(), s.end());
        m[s]++;
    }
    ans = 0;
    for (auto &p : m) {
        ans += (p.second * (p.second - 1)) >> 1;
    }
    cout << ans << endl;
}

int main() {
    fast_io; cout_precision;
    ll t = 1; // cin >> t;
    for (ll i = 0; i < t; i++) {
        func();
    }
}

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

int n;
int a[110];

template<class T>
T f(T x){
    T res = 0;
    for(int i = 0; i < n; ++i){
        T d = a[i] - x;
        res += d*d;
    }
    return res;
}

int main(){
    while(cin >> n){
        for(int i = 0; i < n; ++i) cin >> a[i];
        double l = -200, r = 200;
        for(int _ = 0; _ < 200; ++_){
            double x1 = (l+l+r)/3;
            double x2 = (l+r+r)/3;
            double y1 = f(x1);
            double y2 = f(x2);
            if(y1 < y2){
                r = x2;
            } else {
                l = x1;
            }
        }
        int x = l;
        cout << min(min(f(x-1),f(x)),f(x+1)) << endl;
    }
}


Measured memory_bytes: 256
import math
a, b, deg = list(map(float, input().split()))
theta = math.radians(deg)

S = a * b / 2 * math.sin(theta)

c = math.sqrt(a**2 + b**2 - 2*a*b*math.cos(theta))
L = a + b + c

h = 2 * S / a

print('{0:.6f}'.format(S))
print('{0:.6f}'.format(L))
print('{0:.6f}'.format(h))


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

vector<long long int> ans(100);
void cal(){
    ans[0] = 2;
    ans[1] = 1;
    for(int i = 2; i < 87; i++){
        ans[i] += (ans[i - 1] + ans[i - 2]);
        //cout << ans[i] << endl;
    }
}

int main(){
    cal();

    int n;
    cin >> n;

    cout << ans[n] << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include <vector>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<bitset>
using namespace std;
using vi = vector<int>;
using vii = vector<vi>;
using vs = vector<string>;
using pii = pair<int, int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep2(i,m,n) for(int i=m;i<n;i++)
#define vsort(v) sort(v.begin(), v.end())
#define rv(v) reverse(v.begin(), v.end())
#define ll long long
#define PI 3.141592653589793A
using vll = vector<ll>;
using Graph = vii;
const ll MOD = 1e9 + 7;

int n;
ll dp[100005];
int h[10000];

int main() {
	ll a, b, k;
	cin >> a >> b >> k;
	ll s, t;
	s = a - k > 0 ? a - k : 0;
	t = k - a > 0 ? (a-k) : 0;
	t += b;
    t=t<0?0:t;
	cout << s << " " << t << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long 
#define float long double 
#define endl '\n'
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

using namespace std;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

const int hell = 1e9+7;
 
signed main(){
	IOS;
	int h , w ;
	cin >> h >> w ;
	string grid[h];
	for(auto& i : grid)
		cin >> i;
	int dp[h][w];
	for(int i=0;i<h;i++)
		for(int j=0;j<w;j++)
			dp[i][j]=0;
	dp[0][0]=1;
	for(int i=0;i<h;i++)
	       	dp[i][0] = (grid[i][0]=='.')?1*(i>0?dp[i-1][0]:1):0;
	for(int i=0;i<w;i++)
		dp[0][i] = (grid[0][i]=='.')?1*(i>0?dp[0][i-1]:1):0;

	debug() << imie(range(dp[0],dp[0]+w));
	for(int i=1;i<h;i++){
		for(int j=1;j<w;j++){
			if(grid[i][j]=='.'){
				(dp[i][j] = dp[i][j-1]+dp[i-1][j])%=hell;
				debug() << imie(i) imie(range(dp[i],dp[i]+w));
			}
		}
	}
	cout << dp[h-1][w-1] << endl; 
	return 0;
}







Measured memory_bytes: 9088
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int N,K;
int dp[2005][2005];
int maxi[2005];
int s[2005];
int nr[2005];
vector<int> G[2005];
void dfs(int nod,int tata)
{
    dp[nod][0]=1;
    maxi[nod]=nr[nod]=1;
    for(auto it:G[nod]){if(tata!=it){dfs(it,nod);nr[nod]+=nr[it];}}
    for(auto it:G[nod])
        if(tata!=it)
        {
            fill_n(s+1,K+1,1<<30);
            s[0]=dp[nod][0]+dp[it][0];
            for(int j=0;j<=maxi[it]&&j<K+1;j++)
                for(int k=1;k<=maxi[nod]&&k<=K+1-j;k++)
                    s[max(k,j+1)]=min(s[max(k,j+1)],dp[nod][k]+dp[it][j]);
            for(int i=1;i<=K+1;i++)s[i]=min(s[i-1],s[i]);
            memcpy(dp[nod],s,sizeof(s));
            maxi[nod]=max(maxi[nod],maxi[it]+1);
        }
}
int main()
{
    cin>>N>>K;
    for(int i=1;i<N;i++)
    {
        int a,b;
        cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(1,0);
    int ans=1<<30;
    for(int i=1;i<=N;i++)
        for(int j=0;j<=K+1;j++)
            ans=min(ans,dp[i][j]+nr[1]-nr[i]);
    cout<<ans;
    return 0;
}


Measured memory_bytes: 16128
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, T;
    cin >> N >> T;
    int A[N];
    rep(i, N) cin >> A[i];
    
    int MX = 0;
    int ans = 0;
    int sub = 0;
    for(int i = N-1; i >= 0; i--) {
        MX = max(MX, A[i]);
        if (MX - A[i] > sub) {
            sub = MX - A[i];
            ans = 1;
        } else if (sub == MX - A[i]) ans++;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 640
read n m c
read -a b
count=0
for i in `seq $n`
do
read -a a
sum=$c
for j in `seq $m`
do
sum=$((a[j-1]*b[j-1]+sum))
done

if [ $sum -gt 0 ]; then
count=$((count+1))
fi
done
echo $count

Measured memory_bytes: 620
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using ll = long long;
using vec = vector<char>;
using vec2 = vector<vector<ll>>;
ll inf = pow(2,62);

int main(){
    ll r;
    cin >> r;
    cout << 2*r*M_PI;
}

Measured memory_bytes: 3668
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define mod 1000000007
using namespace std;
typedef long long ll;
template<class T> using V=vector<T>;
using Graph = vector<vector<int>>;
using P=pair<ll,ll>;
typedef unsigned long long ull;
typedef long double ldouble;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//V,P(大文字)使用不可

const ll INF=1000000000000000000;

signed main(){
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    cout<<max(a*b,c*d)<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rev(i, n) for(int i = (int)(n - 1); i >= 0; i--)
#define rev1(i, n) for(int i = (int)(n); i > 0; i--)
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define resort(v) sort((v).rbegin(), (v).rend())
#define vi vector<int>
#define vvi vector<vector<int>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
using ll = long long;
using P = pair<int, int>;
/* ----------------よく使う数字や配列----------------- */
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
constexpr ll mod = 1e9+7;
constexpr ll inf = LLONG_MAX;
constexpr long double eps = DBL_EPSILON;
constexpr long double pi = 3.141592653589793238462643383279;
/* ----------------------end----------------------- */

/* --------------------ライブラリ-------------------- */
ll fact(int i) {       //階乗
    if (i == 0) return 1;
    return (fact(i - 1)) * i;
}
ll gcd(ll a, ll b) {        //最大公約数
    if(b == 0) return a;
    return gcd(b, a % b); 
}
ll lcm(ll a, ll b) {      //最小公倍数
    return a * b / gcd(a, b);
}
int keta(ll n) {        //桁数を求める
    if(n == 0) return 1;
    int count = 0;
    while(n != 0) {
        n /= 10;
        count++;
    }
    return count;
}
ll ketasum(ll n) {    //各桁の和
    ll sum = 0;
    while(n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
/* ----------------------end----------------------- */


int main() {
    string s;cin >>s ;
    cout << s[0] << s.size()-2 << s[s.size()-1] << endl;;
    return 0;
}

Measured memory_bytes: 3596
import java.util.*;
public class Main {
	public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
	String N = sc.next();
	String kakera = "";
	int max_length = 0;
	for(int i = 2;i < N.length();i += 2){
		kakera = N.substring(0,i);
		if(kakera.substring(0,i/2).equals(kakera.substring(i/2,i))){
			max_length = i;
		}		
	}
	System.out.println(max_length);
	}
}
	


Measured memory_bytes: 23124
program probC
  implicit none
  integer*8,allocatable :: ame(:,:)
  integer*8 N,j,tot,tmp

  read(*,*) N
  allocate(ame(1:n,2))
  ame=0

  read(*,*) ame(1:n,1)
  read(*,*) ame(1:n,2)


  tot=0
  tmp=0
  
  do j=1,n
     tmp=sum(ame(1:j,1))+sum(ame(j:n,2))
     if(tot<tmp) tot=tmp
  end do
  
  write(*,*) tot
  
end program probC


Measured memory_bytes: 768
#include <bits/stdc++.h>
#include <cassert>
typedef long long int ll;
using namespace std;

#if defined(DEBUG)

#include <unistd.h>
#include <sys/fcntl.h>
#define DLOG(...)        cerr << dbgFormat(__VA_ARGS__) << endl
#define DCALL(func, ...) func(__VA_ARGS__)

template <class... Args>
string dbgFormat(const char* fmt, Args... args) {
  size_t len = snprintf(nullptr, 0, fmt, args...);
  char buf[len + 1];
  snprintf(buf, len + 1, fmt, args...);
  return string(buf);
}

#else  // defined(DEBUG)

#define DLOG(...)
#define DCALL(func, ...)

#endif // defined(DEBUG)

int main(int argc, char *argv[]) {
#if defined(DEBUG)
  // GDB on Cygwin ignores redirection at run command.
  if (argc == 2) dup2(open(argv[1], 0), 0);
#else
  // For performance.  We should not use C-style stdio functions
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  cout << setprecision(20);

  int N; cin >> N;
  vector<int> H(N);
  for (int i = 0; i < N; i++) cin >> H.at(i);
  int xMin = (int)1e9 + 10;
  for (int i = N - 1; i >= 0; i--) {
    if (H.at(i) > xMin + 1) {
      cout << "No\n";
      return 0;
    }
    xMin = min(xMin, H.at(i));
  }
  cout << "Yes\n";

  return 0;
}



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

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

    ll i,j,k,l,m,n,w,x,y,z,p,q,tmp,sum=0;
    ll a[100000];
    string str;
    cin>>n>>x>>y;;
    x--;
    y--;
    rep(i,n-1){
        REP(j,i+1,n){
            a[min(j-i,abs(j-y)+1+abs(x-i))]++;
            //cout<<i<<" "<<j<<" "<<min(j-i,abs(j-y)+1+abs(x-i))<<endl;
        }
    }
    rep(i,n){
        if(i==0) continue;
        cout<<a[i]<<endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include "bits/stdc++.h"
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()



int main() {
    int N,L;
    cin>>N>>L;
    vector<string> S(N);
    for(int i=0;i<N;i++)
        cin>>S.at(i);
    sort(S.begin(),S.end());
    for(int j=0;j<N;j++)
        cout<<S[j];
    cout<<endl;
}

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

#define MP make_pair
#define PB push_back
#define ALL(x)      (x).begin(),(x).end()
#define REP(i,n)    for(int i=0;i<(n);i++)
#define REP1(i,n)   for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n)   for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))
 
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI > VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;
 
const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;
 
const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

template< typename T >
struct edge {
  int src, to;
  T cost;

  edge(int to, T cost) : src(-1), to(to), cost(cost) {}

  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator int() const { return to; }
};

template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WeightedGraph = vector< Edges< T > >;
using UnWeightedGraph = vector< vector< int > >;
template< typename T >
using Matrix = vector< vector< T > >;

template< typename T >
pair< T, int > dfs(const WeightedGraph< T > &g, int idx, int par) {
  pair< T, int > ret(0, idx);
  for(auto &e : g[idx]) {
    if(e.to == par) continue;
    auto cost = dfs(g, e.to, idx);
    cost.first += e.cost;
    ret = max(ret, cost);
  }
  return ret;
}

template< typename T >
T tree_diameter(const WeightedGraph< T > &g) {
  auto p = dfs(g, 0, -1);
  auto q = dfs(g, p.second, -1);
  return (q.first);
}

void solve(long long N, std::vector<long long> a, std::vector<long long> b){
    WeightedGraph< int > g(N);
    REP(i, N-1) {
        g[a[i]-1].emplace_back(b[i]-1, 1);
        g[b[i]-1].emplace_back(a[i]-1, 1);
    }

    int len = tree_diameter(g) + 1;
    if(len == 1) { cout << "First" << endl; }
    else if(len == 2) { cout << "Second" << endl; }
    else if((len-2)%3==0) { cout << "Second" << endl; }
    else { cout << "First" << endl; }
}

int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> a(N-1);
    std::vector<long long> b(N-1);
    for(int i = 0 ; i < N-1 ; i++){
        scanf("%lld",&a[i]);
        scanf("%lld",&b[i]);
    }
    solve(N, std::move(a), std::move(b));
    return 0;
}


Measured memory_bytes: 29952
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int a,b,s=0;
    cin >> b >> a;
    long long int arr[b];
    for(long long int i=0; i<b; i++)
    {
        cin >> arr[i] ;
        //s=s+arr[i];
    }
    sort(arr,arr+b);

    if(a==0)
    {
        for(int i=0; i<b; i++)
        {
            //cout << arr[i] << " ";
            s=s+arr[i];
        }
    }else{
    for(int i=0; i<b-a; i++)
        {
            //cout << arr[i] << " ";
            s=s+arr[i];
        }
    }

    cout << s << endl;

    return 0;
}


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

using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVC vector<vector<char>>
#define fore(i,a) for(auto &i:a)

typedef pair <int, int> P;
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
const int  INF = 1 << 30;
const ll INFL = 1223372036854775807;
const ll mod = 1000000007;		








int main() {
	
	int n;
	cin >> n;
	
	vector<pair<int, int>> v;
	REP(i, n) {
		int a;
		cin >> a;
		v.push_back({ a,1 });
	}
	REP(i, n) {
		int b;
		cin >> b;
		v.push_back({ b,-1 });
	}

	sort(ALL(v));

	ll ans = 1;
	ll res = 0;

	REP(i, 2 * n) {
		int j = v[i].second;

		if (res*j<0){
			ans *= abs(res);
			ans %= mod;		
		}
		res += j;
	}

	cout << ans << endl;

	return 0;

}

Measured memory_bytes: 2420
#include <iostream>
using namespace std;
 
int main(){
    int a, b;
    int price = 100000;

    cin >> a;
    for (int i = 0; i < a; i++) {
        price *= 1.05;
        b = price % 1000;
        if (b != 0) {
            price += 1000;
            price -= b;
        }
    }
    cout << price << endl;

    return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N, M; cin >> N >> M;
  vector<int> L(M);
  vector<int> R(M);
  for(int i=0;i<M;i++){
    cin >> L.at(i) >> R.at(i);
  }
  sort(L.begin(), L.end());
  sort(R.begin(), R.end());
  if(L.at(M-1)>R.at(0)){
    cout << 0 << endl;
  }
  else cout << R.at(0)-L.at(M-1)+1;
}

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

using namespace std;
typedef long long ll;
#define rep(i, j, n) for (int i = j; i < n; i++)
#define out(ans) cout << ans << endl;
const long long mod = 1e9 + 7;

int main(){

  int a,b,c,d;cin>>a>>b>>c>>d;

  if(a>b)swap(a,b);
  if(c>d)swap(c,d);

  out(a+c);

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define LL long int
#define ULL unsigned long int
#define LD long double

LL MOD = 1000000007;


int main(){
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; ++i) cin >> v[i];
    sort(v.begin(),v.end(),greater<int>());

    long int ans = v[0];
    int l = 1;
    for(int i = 0; i < n - 2; i++){
        ans += v[l];
        if(i % 2 == 1) l++;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 4028
#include <limits>
using ll          = long long;
constexpr int INF = std::numeric_limits<int>::max() / 2;
constexpr ll LNF  = std::numeric_limits<ll>::max() / 2;

#ifndef DEBUG_HPP_OB5Y82L9
#define DEBUG_HPP_OB5Y82L9

#ifdef PA_DEBUG
#define PD(stmt) stmt
#else
#define PD(stmt)
#endif

#endif /* end of include guard: DEBUG_HPP_OB5Y82L9 */


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

template <typename T>
void print(vector<T> const &x, string s = "") {
    PD(cerr << s);
    PD(copy(x.begin(), x.end(), ostream_iterator<ll>(cerr, ", ")));
    PD(cerr << endl);
}

ll compute(vector<ll> v, int K, int Q, vector<int> &seps) {
    int N = v.size();
    sort(seps.begin(), seps.end());
    seps.push_back(N);
    print(seps, "seps: ");
    for (int i = 1; i < (int)seps.size(); i++) {
        sort(v.begin() + seps[i - 1] + 1, v.begin() + seps[i]);
    }
    print(v, "sorted v: ");

    vector<ll> ans;
    ans.reserve(N);
    for (int i = 1; i < (int)seps.size(); i++) {
        ans.insert(ans.end(), v.begin() + seps[i - 1] + 1,
                   v.begin() + seps[i - 1] + 1 +
                       max(0, seps[i] - seps[i - 1] - 1 - K + 1));
    }
    print(ans, "ans: ");
    auto a = *min_element(ans.begin(), ans.end());
    nth_element(ans.begin(), ans.begin() + Q - 1, ans.end());
    sort(ans.begin(), ans.end());
    seps.pop_back();
    return Q <= (int)ans.size() ? ans[Q - 1] - a : LNF;
}

int main() {
    int N, K, Q;
    cin >> N >> K >> Q;
    vector<ll> orig(N);
    for (int i = 0; i < N; i++) { cin >> orig[i]; }

    vector<pair<ll, int>> cp(N);
    for (int i = 0; i < N; i++) {
        cp[i].first  = orig[i];
        cp[i].second = i;
    }
    sort(cp.begin(), cp.end());

    vector<int> seps = {-1};
    ll mi            = compute(orig, K, Q, seps);
    for (auto const &p : cp) {
        seps.push_back(p.second);
        ll res = compute(orig, K, Q, seps);
        if (res == LNF) break; // ??????
        mi = min(mi, res);
    }
    cout << mi << endl;
    return 0;
}


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

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

struct rec {
	double dist;
	int pos, ticket;
	const bool operator<(const rec& r) const {
		if (dist != r.dist) return dist > r.dist;
		if (ticket != r.ticket) return ticket < r.ticket;
		return pos < r.pos;
	}
};

int main() {
	cin.sync_with_stdio(false); cin.tie(0);
	cin.exceptions(cin.failbit);

	for (;;) {
		int n, m, p, a, b; cin >> n >> m >> p >> a >> b; if (!n) break;
		vi t(n); rep(i, 0, n) cin >> t[i];
		vector<vector<pii>> G(m + 1, vector<pii>());
		rep(i, 0, p) {
			int x, y, z; cin >> x >> y >> z;
			G[x].push_back({y, z}); G[y].push_back({x, z});
		}
		sort(all(t));
		double ans = 1e9;
		do {
			vector<vector<double>> dist(m + 1, vector<double>(n + 1, 1e9));

			dist[a][0] = 0.0;

			priority_queue<rec> pq;
			pq.push(rec { 0.0, a, 0 });

			while (!pq.empty()) {
				rec r = pq.top(); pq.pop();
				if (r.dist > dist[r.pos][r.ticket]) continue;
				if (r.pos == b) break;
				if (r.ticket == n) continue;

				for (pii h : G[r.pos]) {
					double nd = r.dist + 1.0 * h.second / t[r.ticket];
					if (nd < dist[h.first][r.ticket + 1]) {
						//cout << h.first << " " << r.ticket + 1 << " " << nd << endl;
						dist[h.first][r.ticket + 1] = nd;
						pq.push(rec { nd, h.first, r.ticket + 1 });
					}
				}
			}

			double v = 1e9;
			rep(i, 0, n + 1) v = min(v, dist[b][i]);
			//rep(i, 0, n) cout << t[i] << " ";
			//cout << ": " << v << endl;
			ans = min(ans, v);
		} while (next_permutation(all(t)));
		if (ans < 1e9) {
			cout << fixed << setprecision(12) << ans << endl;
		} else {
			cout << "Impossible" << endl;
		}
	}
}



Measured memory_bytes: 3348
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.HashSet;
import java.util.Scanner;

public class Main {

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

//    Scanner cin = new Scanner(new FileReader("input.txt"));
    Scanner cin = new Scanner (System.in);

    int num = cin.nextInt();
    int numTemp = 0;
    for (int i=1;i<=9;i++){
      numTemp = i+i*10+i*100;
      if (numTemp >= num) break;
    }
    System.out.println(numTemp);

  }


}

Measured memory_bytes: 23124
n,m=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr,reverse=True)
acum=[arr[0]]
for i in range(1,n):
  acum.append(acum[-1]+arr[i])
l=0
r=2*10**5+1
while r-l!=1:
  mid=(l+r)//2
  tmp=0
  cnt=0
  pos=n-1
  for i in range(n):
    while pos!=-1:
      if arr[i]+arr[pos]>=mid:
        cnt+=pos+1
        tmp+=arr[i]*(pos+1)+acum[pos]
        break
      else:
        pos-=1
        if pos==-1:
          break
  if cnt<=m:
    r=mid
  else:
    l=mid
tmp+=(m-cnt)*l
print(tmp)

Measured memory_bytes: 14152
/**
 * Created by luzhou on 3/20/17.
 */
import java.util.*;
class Main {
    public static void main(String[] args){
        Scanner read = new Scanner(System.in);
        int x = Integer.parseInt(read.nextLine());
        int c = 0;
        int sum = 0;
        while (sum < x){
            c++;
            sum += c;
        }

                System.out.println(c);

    }
}


Measured memory_bytes: 21076
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld  double
#define mod 1000000007
int n,m;
ld arr[10000];
ld dp[2999+9][2999+9];
int main() {
    cin>>n>>m;
    for(int i = 0;i<n;i++){
        cin>>arr[i];
    }
    dp[0][0] = 1;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            dp[i+1][j+1] = dp[i][j] * arr[i];
            dp[i+1][j] +=dp[i][j] * (1-arr[i]);
        }
    }
    ld ans = 0;
    for(int i = (n+1)/2 ; i<=n;i++){
        ans+= dp[n][i];
    }
    cout << fixed << setprecision(9) << ans << endl;
    return 0;
}


Measured memory_bytes: 70784
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from itertools import accumulate
from collections import deque, defaultdict
def main():
    n, ko = map(int, input().split())
    p = tuple(map(int, input().split()))
    c = tuple(map(int, input().split()))

    scores_all = deque()
    for k1 in range(n):
        scores = deque()
        kita = defaultdict(int)
        kita[k1] = ko
        cnt = ko - 1
        koko = p[k1] - 1
        scores.append(c[koko])
        kita[koko] = cnt
        while cnt:
            cnt -= 1
            koko = p[koko] - 1
            scores.append(c[koko])
            if kita[koko]:
                break
            else:
                kita[koko] = cnt
        cycle_long = kita[koko] - cnt
        scores_a = tuple(accumulate(scores))

        if cnt:
            if scores_a[-1] > 0:
                kaisuu = ko // cycle_long
                s1 = scores_a[-1] * kaisuu
                amari = ko % cycle_long
                if amari:
                    t = max(0, max(scores_a[:amari]))
                    s1 += t
                s2 = scores_a[-1] * (kaisuu - 1)
                s2 += max(scores_a)
                scores_all.append(max(s1, s2))
            else:
                scores_all.append(max(scores_a))
        else:
            scores_all.append(max(scores_a))
    print(max(scores_all))

if __name__ == '__main__':
    main()

Measured memory_bytes: 222372
# 幅W, 高さH, 点の数N
W, H, N = map(int, input().split())

# ゼロ(白)で埋めた2次元配列
tmp = [[0] * W for i in range(H)]
tmp

# N回塗りつぶす
for n in range(N):
    # 塗る場所を入力する
    X,Y,A = map(int, input().split())
    
    if A == 1:
        # xより左を塗る
        for y in range(0,H):
            for x in range(0,X):
                tmp[y][x] = 1

    if A == 2:
        # xより右を塗る
        for y in range(0,H):
            for x in range(X,W):
                tmp[y][x] = 1
                
    if A == 3:
        # yより下を塗る
        for y in range(0,Y):
            for x in range(0,W):
                tmp[y][x] = 1
                
    if A==4:
        # yより下を塗る
        for y in range(Y,H):
            for x in range(0,W):
                tmp[y][x] = 1

#print(tmp)
# ゼロの数を数えると、塗りつぶされていないエリアの面積がわかる
result = 0
for y in range(0,H):
    for x in range(0,W):
        if tmp[y][x] == 0:
            result += 1
print(result)

Measured memory_bytes: 3064
class Dice:
    def __init__(self, num_list):
        self.faces = num_list

    def find_rf(self, top, front):
        tf = str(self.faces.index(top)) + str(self.faces.index(front))
        if tf in '12431':
            return self.faces[0]
        elif tf in '03520':
            return self.faces[1]
        elif tf in '01540':
            return self.faces[2]
        elif tf in '04510':
            return self.faces[3]
        elif tf in '02530':
            return self.faces[4]
        else:
            return self.faces[5]

num_list = tuple(map(int, input().split()))

dice = Dice(num_list)

q = int(input())

for i in range(q):
    top, front = map(int, input().split())
    right_face = dice.find_rf(top, front)
    print(right_face)

Measured memory_bytes: 7752
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define rep(i,m,n) for(int (i)=(int)(m);(i)<(int)(n);++(i))
#define rREP(i,m,n) for(int (i)=(n)-1;(i)>=(m);--(i))
#define all(x) (x).begin(),(x).end()
#define out(y,x,h,w) (y)<0||(x)<0||(y)>=(h)||(x)>=(w)
constexpr int INF = 1000000001;
constexpr ll mod = 1000000007;
constexpr double PI = 3.1415926535897932;

template<class T>inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T>inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
inline void init() {
	cin.tie(nullptr); cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

int main() {
	init();

	int N, K; cin >> N >> K;
	string s = "1";
	rep(i, 0, N) {
		char ch; cin >> ch;
		s.push_back(ch);
	}
	int ans = 0;
	int right = 0, zerocnt = 0;
	rep(i, 1, N + 1) {
		while (right < N && zerocnt <= K) {
			if (s[right] == '1' && s[right + 1] == '0') {
				if (zerocnt == K)break;
				else {
					zerocnt++;
					right++;
				}
			}
			else right++;
		}
		chmax(ans, right - i + 1);
		if (i < N - 1 && s[i] == '0' && s[i + 1] == '1')zerocnt--;
	}
	cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 512
from collections import deque

H, W, K = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
c = list(list(input())for _ in range(H))
cost = [[H*W+1]*W for _ in range(H)]
cost[x1-1][y1-1] = 0
queue = deque([[x1-1,y1-1]])
while queue:
    x,y = queue.popleft()
    for vecx,vecy in [[0,1],[1,0],[-1,0],[0,-1]]:
        for k in range(1,K+1):
            nx,ny = x+k*vecx, y+k*vecy
            if not(0<=nx<H) or not(0<=ny<W):
                break
            if c[nx][ny] == '@':
                break
            if cost[nx][ny] > cost[x][y]+1:
                cost[nx][ny] = cost[x][y]+1
                queue.append([nx,ny])
            elif cost[nx][ny] < cost[x][y]+1:
                break
if cost[x2-1][y2-1] == H*W+1:
    print(-1)
else:
    print(cost[x2-1][y2-1])




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

using namespace std;

typedef long long ll;

const int MOD = 1000000007;
const int MAXN = 100003;
const int STATES = 2;

int N;
vector<int> edges[MAXN];
int dp[MAXN][STATES];

int add(int a, int b) {
  return (a + b) % MOD;
}
int mul(int a, int b) {
  return (ll(a) * ll(b)) % MOD;
}
int solve(int u, int parent, bool black) {
  if(parent > 0 && edges[u].size() == 1) return 1;
  if(dp[u][black]) return dp[u][black];

  int ans = 1;
  if(black) {
    for(int v: edges[u]) {
      if(v == parent) continue;

      ans = mul(ans, solve(v, u, 0));
    }
  } else {
    for(int v: edges[u]) {
      if(v == parent) continue;

      ans = mul(ans, add(solve(v, u, 0), solve(v, u, 1)));
    }
  }
  
  return dp[u][black] = ans;
}

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

  cin >> N;
  for(int i = 0; i < N - 1; ++i) {
    int u, v;
    cin >> u >> v;

    edges[u].push_back(v);
    edges[v].push_back(u);
  }

  int ans = add(solve(1, -1, 0), solve(1, -1, 1));
  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 16708
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int i;
	long long x;
	cin>>x;
	long long y=100,j;
	for(i=1;i<10000;i++)
	{
		j=y*0.01;
		y+=j;
		if(y>=x)break;
	}
	cout<<i;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define IOS ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define pf push_front
#define PI acos(-1)
#define EPS 1e-5
#define sz(v) ((int)(v).size())
#define all(v) v.begin(),v.end()
#define forn(i, n) for(ll i=0;i<(ll)n;i++)
#define fi first
#define se second
 

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



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

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

  int ans = 0;
  int odd = 0;
  int even = 0;
  for (int i = 0; i < M; i++){
    odd += i;
  }
  for (int i = 0; i < N; i++){
    even += i;
  }
  
  ans += odd;
  ans += even;
    
    cout << ans << endl;
  
}

Measured memory_bytes: 256