akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)

using namespace std;

typedef long long ll;

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

	int n, m;
	cin >> n >> m;

	vector<bool> ac(n+1,false);
	int accnt = 0;
	vector<int> wa(n+1, 0);
	rep(i, m){
		int p;
		string s;
		cin >> p >> s;
		if(s == "AC"){
			if(!ac[p]){
				ac[p] = true;
				accnt++;
			}
		}else{
			if(!ac[p]){
				wa[p]++;
			}
		}
	}

	int wacnt = 0;
	rep(i, n) if(ac[i+1]) wacnt += wa[i+1]; 
	cout << accnt << " " << wacnt << endl;
}


Measured memory_bytes: 768
import sys
readline = sys.stdin.readline

N, M = map(int, readline().split())

Edge = [[] for _ in range(N)]
for _ in range(M):
    u, v, c = map(int, readline().split())
    u -= 1
    v -= 1
    Edge[u].append((v, c))
    Edge[v].append((u, c))

A = [None]*N
A[0] = (1, 0)
stack = [0]
used = set([0])
inf = 10**20
def f():
    h = None
    while stack:
        vn = stack.pop()
        a, b = A[vn]
        for vf, c in Edge[vn]:
            if vf not in used:
                A[vf] = (-a, c-b)
                stack.append(vf)
                used.add(vf)
            else:
                af, bf = A[vf]
                if a + af == 0:
                    if not b + bf == c:
                        return 0
                elif h is not None:
                    if not (a+af)*h + b + bf == c:
                        return 0
                else:
                    h2 = (c-b-bf)
                    if 1&h2:
                        return 0
                    h = h2//(a+af)
    if h is not None:
        B = [a*h + b for (a, b) in A]
        if all(b > 0 for b in B):
            return 1
        return 0
    else:
        mi = 0
        ma = inf
        for a, b in A:
            if a == 1:
                mi = max(mi, -b)
            if a == -1:
                ma = min(ma, b)
        return max(0, ma-mi-1)
print(f())   

Measured memory_bytes: 78768
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

s=int(input()); n=len(str(s))
k=int(input())
S=[int(i) for i in str(s)]
dpl=[[0]*(k+1) for i in range(n+1)]
dpj=[[0]*(k+1) for i in range(n+1)]
dpj[0][0]=1
for i in range(n):
    for j in range(k+1):
        dpj[i+1][j] += dpj[i][j]*(S[i]==0)
        dpl[i+1][j] += dpl[i][j] + dpj[i][j]*(S[i] >= 1)
        if j+1 < k+1:
            dpj[i+1][j+1] += dpj[i][j]*(S[i] > 0)
            dpl[i+1][j+1] += dpl[i][j]*9 + dpj[i][j]*max(0,S[i]-1) 

print(dpl[n][k]+dpj[n][k])
# print(dpl)
# print(dpj)

Measured memory_bytes: 38256
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    r, g, b = ns()
    k = ni()

    for i in range(k):
        if r >= g:
            g *= 2
        elif g >= b:
            b *= 2

    if r < g < b:
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()


Measured memory_bytes: 11228
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n,m;
queue <int> Q;
vector <int> gin[5001];
vector <int> gout[5001];
vector <int> ans;
int sta[5001];
int flg = 0;

void bfs(){
  
  int f = 0;
  for(int i=1;i<=n;i++){
    if(gin[i].size()==0) Q.push(i),f++;
  }
  
  if(f >= 2) flg = 1;  
 
  while(!Q.empty()) {
    int t = Q.front();
    Q.pop();
    ans.push_back(t);
   
    f = 0;
    for(int i=0;i<gout[t].size();i++){
      int nx = gout[t][i];
	for(int j=0;j<gin[nx].size();j++){
	  if(gin[nx][j] == t) gin[nx].erase(gin[nx].begin()+j);
	  }
	if(gin[nx].size() == 0){
	  Q.push(nx);
	  f++;
	}
    }
    if(f>=2) flg = 1;
  }
}
	  
	  
int main() {
	  
  cin >> n >> m;

  for(int i=0;i<m;i++) {
    int a,b;
    cin >> a >> b;
    gout[a].push_back(b);
    gin[b].push_back(a);
  }

  bfs();
  
  for(int i=0;i<ans.size();i++)cout << ans[i] << endl;
  if(flg == 1) cout << 1 <<endl;
  else cout << 0 <<endl;
  
  return 0;
  
}

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

using namespace std;

typedef long long LL;
typedef unsigned long long uLL;
typedef long double ldb;
typedef pair<int,int> pii;

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int ans = 1e9;
    int n;
    cin>>n;
    while(n--)
    {
        int a;
        cin>>a;
        int c = 0;
        while(a%2==0)
        {
            ++c;
            a /= 2;
        }
        ans = min(c, ans);
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;


public class Main {
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		int c[] = new int[N];
		
		for(int i =0; i<2*M ; i++){
			int a = sc.nextInt();
			c[a-1]++;
		}
		
		for(int j =0; j<N; j++){
			System.out.println(c[j]);
		}
		
		
		
		
	}
}


Measured memory_bytes: 22996
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <numeric>

std::vector<size_t> make_vector(size_t n, size_t x) {
  return std::vector<size_t>(n, x);
}

template <class Tp>
std::vector<Tp> make_vector(size_t n, const Tp& x) {
  return std::vector<Tp>(n, x);
}

template <class... Ts>
auto make_vector(size_t n, size_t m, const Ts&... x) {
  return std::vector<decltype(make_vector(m, x...))>(n, make_vector(m, x...));
}

int main() {
  size_t N;
  scanf("%zu", &N);

  std::vector<intmax_t> a(N);
  for (auto& ai: a) scanf("%jd", &ai);

  auto dp = make_vector(N, N, intmax_t(0));
  for (size_t i = 0; i < N; ++i)
    dp[i][i] = 0;

  for (size_t w = 1; w < N; ++w)
    for (size_t i = 0; i+w < N; ++i) {
      intmax_t cur = 1e18;
      for (size_t j = i; j < i+w; ++j)
        cur = std::min(cur, dp[i][j]+dp[j+1][i+w]);

      for (size_t j = i; j <= i+w; ++j)
        cur += a[j];

      dp[i][i+w] = cur;
    }

  printf("%jd\n", dp[0][N-1]);
}


Measured memory_bytes: 1536
#include <cstdio>
using namespace std;
char s[10010];
int main(){
    int n;
    scanf("%d", &n);
    scanf("%s", s);
    for(int i = 0; s[i] != '\0'; i ++){
        s[i] = ((s[i] - 'A') + n) % 26 + 'A';
    }
    printf("%s\n", s);
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <numeric>
#include <random>
#include <algorithm>
#include <functional>
#include <cassert>

using namespace std;
typedef long long ll;

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;
}

const int INF = (1 << 30) - 1;
const ll INFLL= (1LL << 61) - 1;
const int MOD = 1000000007;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int N;
  cin>>N;
  if(N%10==3){
    cout<<"bon"<<endl;
  }else if(N%10==0  || N%10==1 ||N%10==6 || N%10==8){
    cout<<"pon"<<endl;
  }else{
    cout<<"hon"<<endl;
  }
}


Measured memory_bytes: 3548
fn input_one<T: std::str::FromStr> () -> Result<T, T::Err> {
    let mut n = String::new();
    std::io::stdin().read_line(&mut n).unwrap();
    n.trim().parse()
}

fn input_arr<T: std::str::FromStr> () -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().flat_map(str::parse).collect()
}

fn main() {
    let n: usize = input_one().unwrap();
    let a: Vec<usize> = input_arr();
    if a.into_iter().all(|v| match v % 2 {
        0 => v % 3 == 0 || v % 5 == 0,
        _ => true
    }) {
        println!("APPROVED");
    } else {
        println!("DENIED");
    }
}


Measured memory_bytes: 2172
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<string,int>;
using T = tuple<string,int,int>;

int main(){
  int n; cin >> n;
  vector<int> v(n),c(n);
  for(int i = 0; i < n; i++) cin >> v[i];
  for(int i = 0; i < n; i++) cin >> c[i];

  int ans = 0;
  for(int bit = 0; bit < (1<<n); bit++){
    int cost = 0, val = 0;
    for(int i = 0; i < n; i++){
      if(bit & (1<<i)){
        cost += c[i];
        val += v[i];
      }
    }
    int temp = val - cost;
    ans = max(ans, temp);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;

int main()
{
    double a, b, c, d, e, f;
    double answer1, answer2;

    while (cin >> a >> b >> c >> d >> e >> f) {
        answer1 = round((e * c - b * f) / (a * e - b * d) * 1000) / 1000;
        answer2 = round((-d * c + a * f) / (a * e - b * d) * 1000) / 1000;
        if (answer1 == 0) answer1 = 0.000;
        if (answer2 == 0) answer2 = 0.000;
        cout << fixed << setprecision(3) << answer1<< " " << answer2 << endl;
    }
    
    return 0;
}

Measured memory_bytes: 1292
"""

https://atcoder.jp/contests/abc173/tasks/abc173_f

森の連結成分数 = 頂点数 - 辺数
なので、ある頂点が存在するLRと辺が存在するLRの数を数えて寄与を出せば終わり

"""

N = int(input())

ans = 0
for i in range(1,N+1):
    ans += i * (N+1-i)

for i in range(N-1):

    u,v = map(int,input().split())

    ans -= min(u,v) * (N+1-max(u,v))

print (ans)


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

using namespace std;
using ll = long long;
using P = pair<int,int>;
const ll mod = 1000000007;


int main()
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << (abs(a - c) <= d || (abs(a - b) <= d && abs(b - c) <= d) ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
n, k = map(int, input().strip().split())
L = list(map(int, input().strip().split()))
L = [v - 1 for v in L]
 
seen = set()
intersec = 0
route=[]
while intersec not in seen:
    seen.add(intersec)
    route.append(intersec)
    intersec = L[intersec]

intersecInd = route.index(intersec)

if k<=intersecInd:
    ans=route[k]
else:
    loopSize = len(route) - intersecInd
    ans = route[(k - intersecInd) % (loopSize) + intersecInd]
 
print(ans + 1)

Measured memory_bytes: 32372
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
int ctoi(char c) {return c-'0';}// char to int
int gcd(ll a,ll b){return b?gcd(b,a%b):a;}//MAX
int lcm(ll a,ll b){return a*b/gcd(a,b);}//MIN
 
int  main(){
int n;
cin >> n;
vector<int>a(n);
for(int i=0;i<n;i++){
    cin >> a.at(i);
}
int ans = 1;
for(int i=0;i<n;i++){
    if(ans==a.at(i))ans++;
}
if(n-ans+1==n)cout << -1<<endl;
else{
    cout << n-ans+1<<endl;
}
}
 


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
using Graph = vector<vector<int>>;

int main() {
	int n, x, y; cin >> n >> x >> y;
	Graph G(n+1);
	for (int i = 0; i < n-1; i++) {
		G[i].push_back(i + 1);
		G[i + 1].push_back(i);
	}
	G[x].push_back(y);
	G[y].push_back(x);

	Graph dist(n, vector<int>(n,2009));
	dist[x-1][y-1] = 1;

	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			int d1 = j - i;
			int d2 = abs(i - x + 1) + 1 + abs(j - y + 1);
			int d = min(d1, d2);
			dist[i][j] = min(dist[i][j], d);
			//cout << i + 1 << " " << j + 1 << " " << dist[i][j] << endl;
		}
	}

	vector<int> ans(n,0);
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			int d = dist[i][j];
			if (d < n) {
				ans[d]++;
			}
		}
	}

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

}



Measured memory_bytes: 16128
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <functional>
#include <climits>

using namespace std;

#define int long long
#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 all(a) begin(a),end(a)
#define fst first
#define scd second
#define PB emplace_back
#define PPB pop_back

using vi=vector<int>;
using pii=pair<int, int>;

bool chmin(int&a,int b){return a>b?(a=b,true):false;}
bool chmax(int&a,int b){return a<b?(a=b,true):false;}
int read(){int a;scanf("%lld",&a);return a;}

signed main()
{
	double W, H, x, y; cin >> W >> H >> x >> y;

	bool f = (x == W / 2) and (y == H / 2);

	printf("%.10f %d\n", W*H/2.0, f?1:0);
}




Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<math.h>

#define rep(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define rrep(i,a,n) for(int (i)=(a);(i)>=(n);(i)--)

#define INF ll 1 << 60
#define MOD 1000000007

typedef  long long ll;

using namespace std;

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

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

int gcd(long long int a,long long int b){
    long long int r;
    if(a < b){
        int tmp;
        tmp = a;
        a = b;
        b = tmp;
    }
    while(r = a % b){
        a = b;
        b = r;
    }
    return a;
}

void Integer_factorization(long long int b,long long int n){
    long long int a = 2;
    long long int count = 0;
    long long int ans = 1;
    long long int ndash = n;
    if(b == 1) cout << n << endl;
    else{
    while(ndash >= a*a){
        if(n % a  == 0){
            count++;
            n/=a;

        if(count % b == 0){
            ans *= a;
        }
        }else{a++;count = 0;}
    }

    cout<<  ans << endl;
    }
}

void ys(){
    cout << "Yes" << endl;
}

void yb(){
    cout << "YES" << endl;
}

void ns(){
    cout << "No" << endl;
}

void nb(){
    cout << "NO" << endl;
}

int dig(int d){
    int ans = 1;
    if(d == 0) return ans;
    while(d != 0){
        d--;
        ans*=100;
    }
    return ans;
}

void solve(void){
    int a,b;
    cin >> a >> b;
    int c = b-a;
    int ans = 0;
    rep(i,1,c){
        ans+=i;
    }
    cout << - a + ans << endl;
}

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
ll N, A, B, C, D;
string S;

bool ok(ll s, ll e) {
    for (int i = s; i < e - 1; i++) {
        if (S[i] == '#' && S[i + 1] == '#') {
            return false;
        }
    }
    return true;
}

int main() {
    cin >> N >> A >> B >> C >> D;
    --A;
    --B;
    --C;
    --D;
    cin >> S;
    if (!ok(A, C) || !ok(B, D)) {
        cout << "No" << endl;
        return 0;
    }
    if (D > C) {
        cout << "Yes" << endl;
        return 0;
    }
    for (int i = (B - 1); i < D; i++) {
        if (S[i] == '.' && S[i + 1] == '.' && S[i + 2] == '.') {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 3720
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll MOD = 1000000007;

int dp[100001][13];

signed main()
{
    string s;
    cin >> s;
    
    int n = s.size();

    dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 13; j++) {
            if (s[i] == '?') {
                for (int k = 0; k < 10; k++) (dp[i+1][(10*j+k)%13] += dp[i][j]) %= MOD;
            } else {
                int k = s[i] - '0';
                (dp[i+1][(10*j+k)%13] += dp[i][j]) %= MOD;
            }
        }
    }
    cout << dp[n][5] << endl;

    return 0;
}


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

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

    int N;
    cin >> N;

    map<string, bool> m;

    for(int i = 0; i < N; i++) {
        string S;
        cin >> S;
        m[S] = true;
    }

    int ans = 0;

    for(auto i = begin(m); i != m.end(); i++) {
        ans++;
    }

    cout << ans << endl;
}

Measured memory_bytes: 19248
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int n = scan.nextInt();
		int m = scan.nextInt();
		
		boolean[][] graph = new boolean[n][n];
		for(int i = 0; i < m; i++) {
			int a = scan.nextInt()-1;
			int b = scan.nextInt()-1;
			graph[a][b] = true;
			graph[b][a] = true;
		}
		scan.close();
		
		boolean[] used = new boolean[n];
		used[0] = true;
		dfs(graph,used,0);
		System.out.println(ans);
	}
	
	static int ans = 0;
	static void dfs(boolean[][] graph, boolean[] used, int n) {
		if(AllTrue(used)) {
			ans++;
			return;
		}
		
		for(int i = 0; i < graph.length; i++) {
			if(graph[n][i] && !used[i]) {
				used[i] = true;
				dfs(graph,used,i);
				used[i] = false;
			}
		}
	}
	
	static boolean AllTrue(boolean[] used) {
		for(boolean bool : used)
			if(!bool) return false;
		
		return true;
	}
}


Measured memory_bytes: 23764
import sys
input = sys.stdin.readline
from collections import *

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
serial = [[0]*N for _ in range(N)]
c = 0

for i in range(N):
    for j in range(i+1, N):
        serial[i][j] = c
        serial[j][i] = c
        c += 1

ins = [0]*c
outs = defaultdict(list)

for i in range(N):
    for j in range(N-2):
        s = serial[i][A[i][j]-1]
        t = serial[i][A[i][j+1]-1]
        ins[t] += 1
        outs[s].append(t)

q = deque([v for v in range(c) if ins[v]==0])
ans = 0

while True:
    nq = deque([])
    
    while q:
        v = q.popleft()
    
        for nv in outs[v]:
            ins[nv] -= 1
        
            if ins[nv]==0:
                nq.append(nv)

    ans += 1
    
    if len(nq)==0:
        break
    
    q = nq

if ins==[0]*c:
    print(ans)
else:
    print(-1)


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

void Main()
{
    int n;
    cin >> n;
    vector<long> d(n+1);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j*i <= n; j++)
        {
            d[j*i]++;
        }
    }

    long sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum += (i+1) * d[i+1];
    }
    
    cout << sum << endl;
}

int main(int argc, char **argv)
{
    Main();
    return 0;
}


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

int main() {
	int n;
	cin >> n;
	vector<int> a(n*2);
	for (auto& e : a) {
		cin >> e;
	}
	sort(a.begin(), a.end());
	int cnt = 0;
	for (int i = 2 * n - 2;i >= 0;i-=2) {
		cnt += a[i];
	}
	cout << cnt << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cassert>
#include <cstring>
#include <climits>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define INF (ll)1e18
#define MOD (ll)1e9 + 7
#define pb push_back

typedef long long ll;
typedef long long int llt;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

char dif = 'A' - 'a';
int mod = 1e9 + 7;
ll inf = 1e18;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a[5];
    for (int i = 0; i < 5;i++){
        cin >> a[i];
    }
    int k;
    cin >> k;
    string ans = "Yay!";
    for (int i = 0; i < 5;i++){
        for (int j = 0; j < 5;j++){
            if(i!=j){
                if(abs(a[i]-a[j])>k)
                    ans = ":(";
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
use std::io::{self, Read};
use std::iter::FromIterator;

trait Source {
    fn next_chr(&mut self) -> char;
    fn next_str(&mut self) -> String;
}

#[allow(dead_code)]
fn from_stdin() -> SourceImpl {
    let mut data = String::new();
    io::stdin().read_to_string(&mut data).expect("Input error");
    from_str(&data)
}

fn from_str(s: &str) -> SourceImpl {
    let data = String::from(s);
    let chars = data.chars().collect::<Vec<char>>().into_iter();
    SourceImpl { chars: chars }
}

struct SourceImpl {
    chars: std::vec::IntoIter<char>,
}

impl Source for SourceImpl {
    fn next_chr(&mut self) -> char {
        self.chars
            .by_ref()
            .skip_while(|c| char::is_whitespace(*c))
            .next()
            .expect("eof")
    }

    fn next_str(&mut self) -> String {
        let it = self
            .chars
            .by_ref()
            .skip_while(|c| char::is_whitespace(*c))
            .take_while(|c| !char::is_whitespace(*c));
        let s = String::from_iter(it);
        if s.is_empty() {
            panic!("eof")
        } else {
            s
        }
    }
}

#[allow(unused_macros)]
macro_rules! input {
    ($src:expr; $($elem:tt)*) => {
        input_inner!($src, $($elem)*)
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($src:expr) => {};
    ($src:expr,) => {};
    ($src:expr, $var:ident : mut $ty:tt $($rest:tt)*) => {
        let mut $var = parse!($src, $ty);
        input_inner!($src $($rest)*)
    };
    ($src:expr, $var:ident : $ty:tt $($rest:tt)*) => {
        let $var = parse!($src, $ty);
        input_inner!($src $($rest)*)
    };
}

#[allow(unused_macros)]
macro_rules! parse {
    ($src:expr, ( $($ty:tt),* )) => {
        ( $(parse!($src,$ty)),* )
    };
    ($src:expr, char) => {
        $src.next_chr()
    };
    ($src:expr, [ $ty:tt; $len:expr ]) => {
        (0..$len).map(|_| parse!($src,$ty)).collect::<Vec<_>>()
    };
    ($src:expr, $ty:tt) => {
        parse_str!($src,$ty)
    };
}

#[allow(unused_macros)]
macro_rules! parse_str {
    ($src:expr, chars) => {
        $src.next_str().chars().collect::<Vec<char>>()
    };
    ($src:expr, $ty:ty) => {
        $src.next_str().parse::<$ty>().expect("Parse error")
    };
}

use std::cmp::min;

fn main() {
    let mut src = from_stdin();
    input! { src;
             n: u64, m: u64,
             ab: mut [(u64,u64); n]
    }

    ab.sort();

    let (_, v) = ab.iter().fold((0, 0), |(c, v), &(a, b)| {
        let k = min(b, m - c);
        (c + k, v + a * k)
    });

    println!("{}", v);
}


Measured memory_bytes: 17656
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=5e18;

vector<pair<char,ll>> rle(string s) {
  vector<pair<char,ll>> res;
  char temp=s[0];
  ll count=0;
  for(ll i=0;i<s.size();i++) {
    if(temp==s[i]) {
      count++;
    }
    else {
      res.push_back(pair<char,ll>(temp,count));
      temp=s[i];
      count=1;
    }
    if(i==s.size()-1) {
      res.push_back(pair<char,ll>(temp,count));
    }
  }
  return res;
}

int main() {
  ll n,k;
  string s;
  cin >> n >> k >> s;
  vector<pair<char,ll>> r=rle(s);
  ll ans=0;
  for(auto p:r) {
    ans+=p.second-1;
  }
  if(r.size()/2>k) {
    ans+=2*k;
  }
  else {
    ans=n-1;
  }
  cout << ans << endl;
}

Measured memory_bytes: 2676
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse = True)
t = 0
res = -1
for i in range(N):
  if t + a[i] < K: t += a[i]
  else: res = i
print(N - res - 1)

Measured memory_bytes: 39248
#include<cstdio>
#include<cstdlib>
#include<cstring>

struct Node{
  int key;
  Node *prev, *next;
};

Node *nil;

Node* listSearch(int key)
{
  Node* cur = nil->next;
  while(cur != nil && cur->key != key)
  {
    cur = cur->next;
  }
  return cur;
}

void init()
{
  nil = (Node*)malloc(sizeof(Node));
  nil->next = nil;
  nil->prev = nil;
}

void printList()
{
  Node *cur = nil->next;
  int i = 0;
  while(1)
  {
    if(cur == nil) break;
    if(i++ > 0) printf(" ");
    printf("%d", cur->key);
    cur = cur->next;
  }
  printf("\n");
}

void deleteNode(Node *t)
{
  if(t == nil)
    return ;
  t->prev->next = t->next;
  t->next->prev = t->prev;
  free(t);
}

void deleteFirst()
{
  deleteNode(nil->next);
}

void deleteLast()
{
  deleteNode(nil->prev);
}

void deleteKey(int key)
{
  deleteNode(listSearch(key));
}

void insert(int key)
{
  Node* x = (Node*)malloc(sizeof(Node));
  x->key = key;
  x->next = nil->next;
  x->prev = nil;
  nil->next->prev = x;
  nil->next = x;
}

int main()
{
  char com[20];
  int np=0, nd=0, n, key, i, size=0;
  scanf("%d", &n);
  init();
  for(i=0; i<n; i++)
  {
    scanf("%s", com);
    if(strlen(com) <= 6)
      scanf("%d", &key);
    if(com[0] == 'i')
    {
      insert(key); np++; size++;
    }
    else if(com[0] == 'd')
    {
      if(strlen(com) > 6)
      {
        if(com[6] == 'F') deleteFirst();
        else if(com[6] == 'L') deleteLast();
      }
      else
      {
        deleteKey(key); nd++;
      }
      size--;   //When key doesn't exist, this can cause size minus 1 by mistake.
    }
  }

  printList();
  return 0;
}



Measured memory_bytes: 33800
#include <iostream>
#include <vector>
using namespace std;
int INF = 100000000;
int main(){
  int n, M = 1000000;
  vector<int> A(M,INF), A_odd(M,INF);
  int t = 1, k = 3;
  A[0] = 0;
  A_odd[0] = 0;
  while(t < 1000000){
    for(int k = 0; k+t < M; ++k){
      A[k+t] = min(A[k]+1,A[k+t]);
      if(t%2) A_odd[k+t] = min(A_odd[k]+1,A_odd[k+t]);
    }
    ++k;
    t *= k;
    t /= (k-3);
  }
  while(cin >> n, n){
    cout << A[n] << " " << A_odd[n] << endl;
  }
  return 0;
}

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

int main() {
	
	int n;
	int p[20];
	int t[20] = { 0 };

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

	int ans = 0;

	for (int i = 0; i < n-2; i++) {
		if (p[i] < p[i + 1] && p[i + 1] < p[i + 2]) {
			if (t[i + 1] == 0) {
				ans++;
				t[i + 1] = 1;
			}
		}
		else if (p[i + 2] < p[i + 1] && p[i + 1] < p[i]) {
			if (t[i + 1] == 0) {
				ans++;
				t[i + 1] = 1;
			}
		}
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#define MAX 100000
#define N -1

typedef struct Node{
  int poo,loo,roo;
}Node;

Node Ty[MAX];

int depth(int);
void p_degree(int);

int main(){

  int i,j,n,node,degree,children,left;

  scanf("%d",&n);

  for(i = 0; i < n; i++){
    Ty[i].poo = N;
    Ty[i].loo = N;
    Ty[i].roo = N;
  }

  for(i = 0; i < n; i++){
    scanf("%d%d",&node,&degree);
    for(j = 0; j < degree; j++){
      scanf("%d",&children);
      Ty[children].poo = node;
      if(j == 0) Ty[node].loo = children;
      else Ty[left].roo = children;
      left = children;
    }
  }

  for(i = 0; i < n; i++){
      printf("node %d: parent = %d, depth = %d, ",i,Ty[i].poo,depth(i));
    
    if(Ty[i].poo == N) printf("root, [");
    else if(Ty[i].loo == N) printf("leaf, [");
    else printf("internal node, [");
    
    p_degree(Ty[i].loo);
    printf("]\n");
  }

  return 0;
}

int depth(int node)
{
  int count = 0;
  
  while(Ty[node].poo != N){
    count++;
    node = Ty[node].poo;
  }
  return count;
}

void p_degree(int i)
{
  if(i != N){
    if(Ty[i].roo == N) printf("%d",i);
    else printf("%d, ",i);
    p_degree(Ty[i].roo);
  }
}
    

Measured memory_bytes: 1784
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define is(a, b) a == b
#define len(v) ll(v.size())

const ll INF = 1LL << 58;

class UnionFind {
public:
	//親の番号を格納する。親だった場合は-(その集合のサイズ)
	vector<int> Parent;
 
	//作るときはParentの値を全て-1にする
	//こうすると全てバラバラになる
	UnionFind(int N) {
		Parent = vector<int>(N, -1);
	}
 
	//Aがどのグループに属しているか調べる
	int root(int A) {
		if (Parent[A] < 0) return A;
		return Parent[A] = root(Parent[A]);
	}
 
	//自分のいるグループの頂点数を調べる
	int size(int A) {
		return -Parent[root(A)];//親をとってきたい
	}
 
	//AとBをくっ付ける
	bool connect(int A, int B) {
		//AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
		A = root(A);
		B = root(B);
		if (A == B) {
			//すでにくっついてるからくっ付けない
			return false;
		}
 
		//大きい方(A)に小さいほう(B)をくっ付けたい
		//大小が逆だったらひっくり返しちゃう。
		if (size(A) < size(B)) swap(A, B);
 
		//Aのサイズを更新する
		Parent[A] += Parent[B];
		//Bの親をAに変更する
		Parent[B] = A;
 
		return true;
	}
};
//x以下の要素への最小index
template <class T> int former(const vector<T> &v, T x) {
  return upper_bound(v.begin(), v.end(), x) - v.begin() - 1;
}
//x以上の要素への最小index
template <class T> int latter(const vector<T> &v, T x) {
  return lower_bound(v.begin(), v.end(), x) - v.begin();
}
//vector書き出し
template <class T1>
void cout_vec(const int n, vector<T1> &vec1){
  rep(i, n){
    cout<<vec1[i]<<' ';
  }
  cout<<'\n';
}
//nCk
ll comb(ll n,ll k){
    ll ans=1;
    FOR(i,n-k+1,n+1){
        ans*=i;
    }
    FOR(i,1,k+1){
        ans/=i;
    }
    return ans;
}
//a,bの最大公約数
ll gcd(ll a,ll b) {
	if (b == 0) return a;
	else return gcd(b, a % b);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin>>s;
    if(s.find("a")!=string::npos && s.find("b")!=string::npos && s.find("c")!=string::npos){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define REP(i, n) for(int i = 1; i < (int)(n); ++i)
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> C(N - 1), S(N - 1), F(N - 1);
    rep(i, N - 1) cin >> C[i] >> S[i] >> F[i];
    
    rep(i, N) {
        int time = 0;
        int now = i;
        while (now < N - 1) {
            int noru;
            if (time < S[now]) noru = S[now];
            else noru = F[now] * ((time + F[now] - 1) / F[now]);
            time = noru + C[now];
            ++now;
        }
        cout << time << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;
using ll = long long;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((int)(x).size())
#define MSG(a) cout << #a << " " << a << endl;

int main()
{
    int n;
    cin >> n;
    vector<int> x(n);
    for (int i = 0; i < n; i++) cin >> x[i];
    int min_p = numeric_limits<int>::max();
    int max_x = *max_element(ALL(x));
    for (int i = 1; i <= max_x; i++) {
        int sum = 0;
        for (int j = 0; j < n; j++) {
            sum += (x[j] - i) * (x[j] - i);
        }
        min_p = min(sum, min_p);
    }
    cout << min_p << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 210;
typedef long long ll;
int n;	
char s[N];
bool vis[N];
int main() {
	
	cin >> n;
	scanf("%s", s + 1);
	int ans = 0;
	for(int i = 1; i < n; i++) {
		for(int j = 1; j <= i; j++) {
			vis[s[j]] = 1;
		}
		int tmp = 0;
		for(int j = i + 1; j <= n; j++) {
			if(vis[s[j]]) tmp++, vis[s[j]] = 0;
		}
		ans = max(ans, tmp);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3212
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mkp make_pair
#define REP(i,n) for(int i=0;i<(n);i++)
#define REPP(i,n,m) for(int i=(n);i<=(m);i++)
int thing[3][150];
int solve(int n){
	int dp[3][150]={0};
	REP(i,2){
		REP(j,n){
			dp[i+1][j+1] = thing[i+1][j+1] + max(dp[i+1][j],dp[i][j+1]);
		}
	}
	return dp[2][n];
}
int main(void){
	int n;
	cin>>n;
	
	REP(i,2){
		REP(j,n){
			cin>>thing[i+1][j+1];
		}
	}
	cout<<solve(n)<<endl;
} 

Measured memory_bytes: 256
h, w = map(int, input().split())
a = [input() for i in range(h)]
for i in range(w + 1) :
    print("#", end="")
print("#")
for i in range(h) :
    print("#" + a[i] + "#")
for i in range(w + 1) :
    print("#", end="")
print("#")



Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repit(it, li) for(auto it=li.begin(); it!=li.end(); it++)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main(){
	int n;
	cin>>n;

	bool ok=false;
	for(int i=1; i<=9; i++) for(int j=1; j<=9; j++){
		if(i*j==n) ok=true;
	}

	if(ok) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}


Measured memory_bytes: 3596
N = int(input())
A = list(map(int,input().split()))

S = []
for i in range(N):
	if i == 0:
		S.append(A[i])
	else:
		S.append(S[i-1] + A[i])
S.append(0)
S.sort()

ans = 0
cnt = 1
cur_s = None
for s in S:
	if cur_s == s:
		cnt += 1
	else:
		ans += cnt * (cnt - 1) // 2
		cnt = 1
		cur_s = s
ans += cnt * (cnt - 1) // 2
print(ans)


Measured memory_bytes: 25976
#include<bits/stdc++.h>
typedef long long ll;
#define dbg          cout<<"Freak"<<endl;
#define dbgg(i)      cout<<i<<endl;
#define N            1e9+7;
#define pb           push_back
using namespace std;
ll t;
ll arr[300005];
vector<ll>v;

int main()
{
    ll a,b,c,d,e,f,g,i,j;
    cin>>t;
    v.pb(0);
    f=0;
    for(i=0;i<t;i++)
    {
        cin>>a;
        v.push_back(a);
        b=abs(a-v[i]);
        f+=b;
    }
    v.pb(0);
    b=abs(0-v[t]);
    f+=b;
    for(i=1;i<=t;i++)
    {
        b=abs(v[i]-v[i-1]);
        c=abs(v[i]-v[i+1]);
        g=f-b-c;
        g=g+abs(v[i+1]-v[i-1]);
        cout<<g<<endl;
    }
    return 0;
}


Measured memory_bytes: 2164
n,m = gets.split.map(&:to_i)
mod = 10 ** 9 + 7

a = []
m.times{a << gets.to_i}
a.sort!
a << 0

dp = Array.new(n+1, 0)
dp[0] = 1

ai = 0
1.upto(n) do |dpi|
    if a[ai] == dpi
        ai += 1
        next
    end

    if dpi == 1
        dp[dpi] = dp[0]
    else
        dp[dpi] = dp[dpi-1] + dp[dpi-2]
    end

    dp[dpi] %= mod if dpi % 10 == 0
end

puts dp[n] % mod

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

using namespace std;
typedef long long ll;

int main(){

 long long n,cnt=0;
 cin>>n;

  long long a[n+1];

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

   for(int i=1;i<=n;i++){
     if(i%2 == 1 && a[i]%2 == 1)
        cnt++;
   }

   cout<<cnt<<endl;

return 0;
}



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

using namespace std;
using LLONG = long long;

int main()
{
    int N;
    cin >> N;
    vector<int> cards(N);
    for (int i = 0; i < N; ++i) cin >> cards[i];
    sort(cards.rbegin(), cards.rend());
    int alice = 0, bob = 0;
    for (int i = 0; i < N; ++i)
    {
        if (i % 2 == 0) alice += cards[i];
        else bob += cards[i];
    }
    cout << alice - bob << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<math.h>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<set>
#include<vector>
using namespace std;

#define INF 1<<21
#define MAX 100005
#define MOD 10e9+7

int main(){
    string s1,s2;
    cin>>s1;
    cin>>s2;
    if(s1[0]==s2[2]&&s1[1]==s2[1]&&s1[2]==s2[0])cout<<"YES"<<endl;
    else cout<<"NO"<<endl;

    return 0;   
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
int a[200005];
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	sort(a+1,a+n+1);
	for (int i=1;i<n;i++){
		if (a[i]==a[i+1]){
			puts("NO");
			return 0;
		}
	}
	puts("YES");
	return 0;
}


Measured memory_bytes: 896
#include<vector>
#include<list>
#include<algorithm>
#include<iostream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
int main(){
  int i,j,k,l;
  int n,p[900];
  p[0]=13;
  j=1;
  for(i=19;i<10000000;i+=10){
    l=(int)sqrt(i)+1;
    for(k=3;k<l;k+=2){
      if(i%k==0||
	 (i-2)%k==0||
	 (i-6)%k==0||
	 (i-8)%k==0)
	break;
    }
    if(k>=l){
      p[j]=i;
      j++;
    }
  }
  while(cin>>n&&n){
    for(i=j-1;p[i]>n;i--);
    cout<<p[i]<<endl;
  }
  return 0;
}

Measured memory_bytes: 868
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		int[]A = new int[5];
		int ans = 0;
		int m = 0;
		for(var i=0;i<5;i++){
			A[i] = int.Parse(Console.ReadLine());
			ans += (A[i]+9)/10*10;
			m = Math.Max(m,(10-A[i]%10)%10);
		}
		ans -= m;
		Console.WriteLine(ans);
	}
}

Measured memory_bytes: 11092
while True:
    S = raw_input()[::-1]
    if S == '0' : break
    m = [1] + [0] * 10
    diff = ans = 0
    even = 1
    for c in S:
        num = int(c)
        diff = (diff + num * even) % 11
        if num : ans += m[diff]
        m[diff] += 1
        even *= -1
    print ans


Measured memory_bytes: 4932
#include <stdio.h>

int main(int argc, char const *argv[])
{
	int n;
	scanf("%d", &n);
	int int_num[n];
	int min, max;
	long long sum = 0;
	
	for (int i = 0; i < n; i++) {
		scanf("%d", &int_num[i]);
		sum += int_num[i];
	
	}
	
	min = int_num[0];
	max = int_num[0];

	for (int i = 0; i < n-1; ++i)
	{
		if (min > int_num[i+1])
			min = int_num[i+1];
		if (max < int_num[i+1])
			max = int_num[i+1];
	}

	printf("%d %d %lld\n", min, max, sum);

	return 0;
}


Measured memory_bytes: 2140
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;

constexpr int INF = numeric_limits<int>::max();

int main()
{
	int N, M, X;
	cin >> N >> M >> X;
	vector<int> C(N);
	vector<vector<int>> A(N, vector<int>(M));
	for (int i = 0; i < N; ++i)
	{
		cin >> C[i];
		for (int j = 0; j < M; ++j)
		{
			cin >> A[i][j];
		}
	}

	int min_cost = INF;
	for (int i = 0; i < 1 << N; ++i)
	{
		vector<int> D(M, 0);
		int cost = 0;
		for (int j = 0; j < N; ++j)
		{
			if ((i & (1 << j)) != 0)
			{
				for (int k = 0; k < M; ++k)
				{
					D[k] += A[j][k];
				}
				cost += C[j];
			}
		}

		bool b = true;
		for (int j = 0; j < M; ++j)
		{
			if (D[j] < X)
			{
				b = false;
				break;
			}
		}

		if (b)
		{
			min_cost = min(min_cost, cost);
		}
	}

	if (min_cost == INF)
	{
		min_cost = -1;
	}
	cout << min_cost << endl;

	return 0;
}

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

int main() {
    int t = 1;
    while(t--)
    {
    	int n, k;
    	cin >> n >> k;
    	int h[n];
    	for(int &val : h) 
    	    cin >> val;
    	int dp[n] = {0};
    	for(int i = 1; i < n; i++)
    	{   
    	    dp[i] = 1e9;
    	    for(int j = 1; j <= min(k, i); j++)
    	    {
    	        dp[i] = min(dp[i], dp[i-j] + abs(h[i]-h[i-j]));
    	    }
    	}
    	cout << dp[n-1];
    }
	return 0;
}

Measured memory_bytes: 4372
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){
  int n;
  bool field[1000][1000] = {false};
  while(cin >>n,n){
    cin.ignore();
    for(int i=0; i<n; i++){
      string l;
      getline(cin,l);
      for(int j=0; j<n; j++){
	if(l[j] == '*'){field[j][i] = 1;}
	else if(l[j] == '.'){field[j][i] = 0;}
      }
    }
    int dp[1000][1000] = {0};
    for(int i=0; i<n; i++){
      for(int j=0; j<n; j++){
	if(field[j][i] == 0){
	  if(i == 0 || j == 0){dp[j][i] = 1;}
	  else{dp[j][i] = min(min(dp[j-1][i],dp[j][i-1]),dp[j-1][i-1])+1;}
	}
      }
    }
    int ans = 0;
    for(int i=0; i<n; i++){
      for(int j=0; j<n; j++){
	if(dp[i][j] > ans){ans = dp[i][j];}
      }
    }
    cout <<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 5816
/*
ID: learnin7
TASK: test
LANG: C++                 
*/
/* LANG can be C++11 or C++14 for those more recent releases */
#include<bits/stdc++.h>

/*  Macros from Endagorion */
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;


int main(){
        
    ios_base::sync_with_stdio(0);
    
    //ofstream fout ("test.out");
    //ifstream fin ("test.in");
    //fin >> a >> b;
    //fout << a+b << endl;
    int n,k;
    double sum=0.0;
    cin>>n>>k;
    int x = min(n,k-1);
    for(int i=1;i<=x;i++){
        int expo = log2((k-1)/i)+1;
        sum += (((double)1/n)*pow(0.5, expo));
    }
    if(n>=k){
        for(int i=k;i<=n;i++){
            sum += ((double)1/n);
        }
    }
    cout<<fixed<<setprecision(12)<<sum<<endl;
    return 0;
}



Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
	int r, d;
	long long x[11];

	cin >> r >> d >> x[0];
	for (int i = 1; i <= 10; i++) {
		x[i] = r * x[i - 1] - d;
		cout << x[i] << endl;
	}
}

Measured memory_bytes: 256
def main():
    X = input()
    if(len(X)<3):
        print(0)
        return
    last = int(X[:len(X)-2])
    two = int(X[-2:])
    if two <= last*5:
        print(1)
    else:
        print(0)

if __name__=='__main__':
    main()


Measured memory_bytes: 2940
#include <iostream>
#include <string>
#include<vector>
#include<algorithm>
#include<math.h>
#include<limits.h>
#include<string>
#include<iomanip>
#include<numeric>
#include<queue>
using namespace std;

long long  mod = 1000000007;

long max(long x, long y) {
	return x > y ? x : y;
}

long min(long x, long y) {
	return x < y ? x : y;
}

long factorial(long n) {
	if (n == 1) {
		return 1;
	}
	else {
		return n * factorial(n - 1);
	}
}

long long  fel(long long  n,long long  f) {

		if (f == 1) {
			return n % mod;
		}
		else if (f % 2 == 0) {
			return (fel(n,f / 2) * fel(n,f / 2)) % mod;
		}
		else {
			return ((n  * fel(n,f / 2) %mod) * fel(n,f / 2))% mod;
		}
	

}


int main()
{
	int a;
	string s, k;
	string t = "";
	cin >> a;
	cin >> s >> k;
	for (int i = 0;i < a;i++) {
		t = t + s[i] + k[i];
	}
	cout << t;
}







Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
  int a,b;
  cin >> a >> b;
  
  int c;
  if(b >= 100)
    c = a * 1000 + b;
  else if(b >= 10)
    c = a * 100 + b;
  else
    c = a * 10 + b;
  
  int ans = 0;
  
  for(int i=0;i<=c;i++){
    if(c == i * i)
      ans++;
  }
  
  if(ans == 0)
    cout << "No" << endl;
  else
    cout << "Yes" << endl;
  
  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
using namespace std;
ll mod = 1e9 + 7;

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

    ll one = 0;
    rep(i,N-1)for(int j=i+1;j<N;j++){
        if(A[i]>A[j]) one += 1;
    }

    ll two = 0;
    rep(i,N)rep(j,N){
        if(A[i]>A[j]) two += 1;
    }

    ll between = two % mod;
    ll nC2 = 0;
    if (K%2 == 0) {
        nC2 = ((K / 2) * (K - 1)) % mod;
    }
    else {
        nC2 = (K * (K - 1) / 2) % mod;
    }
    ll ans = ((one * K) % mod + (between * nC2) % mod) % mod;
    cout << ans << endl;
}


Measured memory_bytes: 256
# coding: utf-8
# Your code here!
N,K=map(int,input().split())
R,S,P=map(int,input().split())
l=list(input())
play=[]

def point(hand):
    if hand=="r":
        return ["p",P]
    elif hand=="s":
        return ["r",R]
    else:
        return ["s",S]

ans=0
for i in range(N)[::-1]:
    if len(play)>=K:
        if point(l[i])[0]==play[-K]:
            if i-K>=0:
                temp=point(l[i-K])[0]
                for item in ["r","s","p"]:
                    if item!=play[-K] and item!=temp:
                        play.append(item)
                        break
            else:
                for item in ["r","s","p"]:
                    if item!=play[-K]:
                        play.append(item)
                        break
        else:
            play.append(point(l[i])[0])
            ans+=point(l[i])[1]
            
    else:
        play.append(point(l[i])[0])
        ans+=point(l[i])[1]
#print(play[::-1])
print(ans)

Measured memory_bytes: 4828
N,Q=map(int,input().split())
lc=[[] for i in range(N)]#二重リストで木を表現
for i in range(N-1):
    a,b=map(int,input().split())
    lc[a-1].append(b-1)
    lc[b-1].append(a-1)
lv=[0 for i in range(N)]#値のリスト
for i in range(Q):
    p,x=map(int,input().split())
    lv[p-1]+=x
lf=[0 for i in range(N)]#訪れたかどうか
#d=collections.deque([0])
lp=[0]#リストをスタックとして用いる
#lp=collections.deque([0])#デキューをスタックorキューとして用いる
lf[0]=1
#for i in range(N):
while len(lp)>0:
    #p=lp[-1]
    p=lp.pop()#リスト・デキューをスタックとして使う
    #p=lp.popleft()#デキューをキューとして使う
    for c in lc[p]:
        if lf[c]==0:
            lv[c]+=lv[p]
            lf[c]=1
            lp.append(c)
for i in range(N-1):
    print(lv[i],end=" ")
print(lv[N-1])


Measured memory_bytes: 106276
package main

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

func main() {
	sc = initScanner(os.Stdin)
	h, w := scanInt(sc), scanInt(sc)
	resolve(h, w)
}

func resolve(h, w int) {
	// header, footer
	tbl := strings.Repeat("#", w+2)
	// body
	body := scanStringSlice(sc, h)

	// 出力開始
	fmt.Println(tbl)
	for _, v := range body {
		fmt.Printf("#%s#\n", v)
	}
	fmt.Println(tbl)
}

// --------------- BASE DEFINITIONS ---------------

const (
	initialBufSize = 100000
	maxBufSize     = 1000000
)

var sc *bufio.Scanner

func initScanner(r io.Reader) *bufio.Scanner {
	buf := make([]byte, initialBufSize)

	sc := bufio.NewScanner(r)
	sc.Buffer(buf, maxBufSize)
	sc.Split(bufio.ScanWords)
	return sc
}

func scanInt(sc *bufio.Scanner) int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}

func scanIntSlice(sc *bufio.Scanner, n int) []int {
	is := make([]int, n)
	for i := 0; i < n; i++ {
		is[i] = scanInt(sc)
	}

	return is
}

func scanString(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

func scanStringSlice(sc *bufio.Scanner, n int) []string {
	ss := make([]string, n)
	for i := 0; i < n; i++ {
		sc.Scan()
		ss[i] = sc.Text()
	}

	return ss
}


Measured memory_bytes: 1796
import collections

def bfs(si, sj, ei, ej):
    q = collections.deque()
    q.append([si, sj, 0])
    used = set()
    used.add((si, sj))
    while len(q) > 0:
        prvi, prvj, cost = q.popleft()
        for i, j in [[prvi + 1, prvj], [prvi - 1, prvj], [prvi, prvj + 1], [prvi, prvj - 1]]:
            if i < 0 or j < 0 or W <= i or H <= j or (i, j) in used:
                continue
            elif grids[j][i] == '.':
                if [i, j] == [ei, ej]:
                    return cost
                else:
                    q.append([i, j, cost + 1])
                    used.add((i, j))
    return -1


H, W = map(int, input().split())
grids = [input() for _ in range(H)]

res = bfs(0, 0, W - 1, H - 1)
if res != -1:
    black_num = sum([row.count('#') for row in grids])
    print( H * W - black_num - 2 - res)
else:
    print(res)

Measured memory_bytes: 3692