akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<numeric>
#include<math.h>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<climits>
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define ll long long
#define pll pair<ll,ll>
#define rep(i,from,to) for(int i=from;i<to;i++)
#define repd(i,from,till) for(int i=from;i>=till;i--)
#define waste ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define inf 1e9+1
#define mod 1e9+7
#define inf1 1e18+1
#define pie 3.14159265358979323846
#define N 100005

using namespace std;

int n,k;
int a[105];
int dp[100005];

int rec(int rem){
//	cout<<rem<<" "<<n<<" "<<k<<endl;
	if(rem<0)return 0;
	if(dp[rem]!=-1)return dp[rem];
	rep(i,0,n){
		int cal=rec(rem-a[i]);
		if(cal) return dp[rem]=0;
	}
	return dp[rem]=1;
}
int solve(){
    cin>>n>>k;
	rep(i,0,n)cin>>a[i];
	rep(i,0,k+1)dp[i]=-1;
	int b=rec(k);
	if(b)cout<<"Second"<<endl;
	else cout<<"First"<<endl;
	return 0;
}
int main(){
    //waste;
    int t;
    // qcin>>t;
    t=1;
    while(t--){
       	solve();
    }
}


Measured memory_bytes: 3712
#[int(i) for i in input().split()]
s = input()
c = 1
if len(s) % 2 != 0:
    print("No")
else:
    for i in range(len(s)//2):
        if s[2 * i:2 * i+2] == "hi":
            c *= 1
        else:
            c *= 0
    if c:
        print("Yes")
    else:
        print("No")


Measured memory_bytes: 38384
import java.io.BufferedReader
import java.util.Arrays

fun main(args: Array<String>) {
    /** comment in when you submit **/
    System.`in`.bufferedReader().use { println(getOutputString(it)) }

    /** delete below after your test **/
    // executeTest()
}

private fun getOutputString(reader: BufferedReader): String {
    val num = reader.readLine().split(" ")[0].toInt()

    var pairs = reader.readLines().map {
        val ints = it.split(" ").map { it.toInt() }
        return@map "${ints[0]}${ints[1]}"
    }
    val origPairs = pairs

    while (pairs.size > 0 && pairs.first().length < num) {
        val newPairs = mutableListOf<String>()
        origPairs.forEach { p1 ->
            pairs.forEach { p2 ->
                val candidate = when {
                    p1.first() == p2.last() -> p2 + p1.substring(1)
                    p1.first() == p2.first() -> p2 + p1.reversed().substring(1)
                    p1.last() == p2.last() -> p1 + p2.reversed().substring(1)
                    p1.last() == p2.first() -> p1 + p2.substring(1)
                    else -> null
                }

                candidate?.let {
                    val chars = it.toCharArray()
                    Arrays.sort(chars)
                    for (i in 0 until chars.size - 1) {
                        if (chars[i] == chars[i + 1]) return@let
                    }

                    newPairs.add(it)
                }
            }
        }

        pairs = newPairs.distinct().sortedBy { it.length }
    }

    return pairs.filter { it.startsWith("1") && it.length == num }.size.toString()
}


Measured memory_bytes: 71328
from collections import defaultdict


class UnionFind():
    # nはノードの数
    def __init__(self, n):
        self.n = n
        self.parents = [-1]*n  # 根のノードは限らないので注意

    # xはノードの番号
    def find(self, x):  # あるノードの親を探すためのメソッド
        if self.parents[x] < 0:  # 親の場合、そのグラフの要素の個数を負の値で保持している
            return x
        else:
            # 再帰的に親を探しにいき、得られた値を格納する
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # x, yはノードの番号
    def union(self, x, y):
        x = self.find(x)  # 根の番号を取得
        y = self.find(y)  # 根の番号を取得
        if x == y:
            return  # 同じ親ならば合体させる必要はない

        # ※ それぞれ要素の個数が負の値で格納されている
        if self.parents[x] > self.parents[y]:
            # yのグループの方が要素の個数が多い場合 (yの方が値が小さいということは、負の世界では値が大きいため)
            # 必ずxの方が要素が多い状態にする
            x, y = y, x

        self.parents[x] += self.parents[y]  # 負の値同士だが、これで良い
        self.parents[y] = x  # yは親ではなくなったため、新しい親であるxの値を正でもつ

    # xはノードの番号
    def size(self, x):
        # 親まで辿ればグループの大きさが負の値で格納されているため、それにマイナスをつけてreturnする
        return -self.parents[self.find(x)]

    # x, yはノードの番号
    def same(self, x, y):
        # 親が同じ = 同じグループに属するならTrueがreturnされる
        return self.find(x) == self.find(y)

    # xはノードの番号
    def members(self, x):
        root = self.find(x)  # 親の値を取得する
        # findで再帰的に親の値が獲得できる
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        # 親となっているノードの番号をリストでreturnする
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_counts(self):
        # グループの数をreturnする
        return len(self.roots())

    def all_group_members(self):
        # 親のノードの番号をキーにして、子のノードの番号を対応させた辞書を返す
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        # printした時の表記
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


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

# 定義するときはUnionFind(要素数)
uf = UnionFind(H*W)
# 木を定義する
for i in range(H):
    for j in range(W):
        if 0 <= i < H-1:  # 最終行でないのであれば実行
            if gridgraph[i][j] != gridgraph[i+1][j]:
                uf.union(W*i+j, W*(i+1)+j)  # 要素の番号の振り方はこうやる

        if 0 <= j < W-1:  # 最終列でないのであれば実行
            if gridgraph[i][j] != gridgraph[i][j+1]:
                uf.union(W*i+j, W*i+j+1)  # 要素の番号の振り方はこうやる

# 根の番号をキーにして、その連結成分に黒, 白それぞれいくつ入っているかを管理する辞書
black = defaultdict(int)
white = defaultdict(int)
for i in range(H):
    for j in range(W):
        if gridgraph[i][j] == "#":
            black[uf.find(W*i+j)] += 1
        else:
            white[uf.find(W*i+j)] += 1
ans = 0
for u in uf.roots():
    ans += black[u] * white[u]
print(ans)


Measured memory_bytes: 32984
#include<bits/stdc++.h>
using namespace std;
int main(){
    int x1,y1,x2,y2;  
    cin>>x1>>y1>>x2>>y2;
    int ans1=x2-(y2-y1);
    int ans2=y2+(x2-x1);
    int ans3=x1-(y2-y1);
    int ans4=y1+(x2-x1);
    
    cout<<ans1<<" "<<ans2<<" "<<ans3<<" "<<ans4<<endl;


}


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

int main(void) {
	llong A, B, C, X, Y;
	cin >> A >> B >> C >> X >> Y;

	llong res = 1LL << 30;
	for (int i = 0; i <= 100000; i++) {
		llong price = i * 2 * C + max(0LL, X - i)*A + max(0LL, Y - i) * B;
		res = min(res, price);
	}

	cout << res << endl;
	return 0;
}

Measured memory_bytes: 256
// Package main provides
//
// File:  c.go
// Author: ymiyamoto
//
// Created on Wed Jan  9 00:33:54 2019
//
package main

import "fmt"

func main() {
	var N int
	fmt.Scan(&N)

	counts := make([]int, 1e5)
	for i := 0; i < N; i++ {
		var a int
		fmt.Scan(&a)
		counts[a]++
	}
	ans := 0
	for i := 0; i+2 < len(counts); i++ {
		n := counts[i] + counts[i+1] + counts[i+2]
		if ans < n {
			ans = n
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 5504
#include <bits/stdc++.h>
using namespace std;
int main() {
  string c;
  cin >> c;
  if (c == "a" || c == "i" || c == "u" || c == "e" || c == "o") {
    cout << "vowel" << endl;
  }
  else {
    cout << "consonant" << endl;
  }
}

Measured memory_bytes: 256
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array
import numpy as np

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


class UnionFind:
    def __init__(self, N):
        self.tree = [-1 for _ in range(N)]

    def root(self, N):
        if self.tree[N] < 0:
            return N
        self.tree[N] = self.root(self.tree[N])
        return self.tree[N]

    def same(self, x, y):
        return self.root(self.tree[x]) == self.root(self.tree[y])

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.tree[x] > self.tree[y]:
            x, y = y, x
        self.tree[x] += self.tree[y]
        self.tree[y] = x

    def size(self, x):
        return -self.tree[self.root(x)]


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    uf = UnionFind(N)
    for _ in range(M):
        a, b = il()
        a -= 1
        b -= 1
        uf.unite(a, b)

    ret = 0
    for n in range(N):
        ret = max(ret, uf.size(n))
    print(ret)


if __name__ == '__main__':
    main()


Measured memory_bytes: 32764
import java.util.Scanner;

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

		// 入力値の取得
		String S = sc.next();

		// 結果の出力
		System.out.println(S.equals("ABC")? "ARC" : "ABC");

		sc.close();
	}
}


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

#define f first
#define s second
#define ins insert
#define eb emplace_back
#define endl '\n'
#define ll long long
#define ld long double
#define vl vector<ll>
#define no cout << "NO" << endl
#define yes cout << "YES" << endl
#define tc ll t; cin >> t; while (t--)
#define sz(c) (ll) (c).size()
#define trav(x,c) for(auto &x : c)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define _for(i,a,n) for(ll i = a ; i < n; ++i)
#define _rfor(i,a,n) for(ll i = n-1 ; i >= a; --i)
#define db(x) cout << #x << ": " << x << endl;
#define _db(c) trav(x,c) cout << x << " "; cout << endl;
#define godspeed ios::sync_with_stdio(0); cin.tie(0);
template<typename... T> void read(T&... x) {((cin >> x),...);}

int main() {
    godspeed;
    int n; cin >> n;
    int a, b, c, d;
    a = b = c = d = 0;

    while(n--) {
    	string s; cin >> s;
    	if (s == "AC") a++;
    	if (s == "WA") b++;
    	if (s == "TLE") c++;
    	if (s == "RE") d++;
    }

    cout << "AC x " << a << endl; 
    cout << "WA x " << b << endl; 
    cout << "TLE x " << c << endl; 
    cout << "RE x " << d << endl; 
}

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

int main() {
  double a,b,h,m;
  cin >> a >> b >> h >>m;
  double sita1,sita2,A;
  if(m == 0){
    sita1 = (h*30.0);
    sita2 = 0;
  }
  else {
    sita1 = (h*30.0 + 30.0*m/60.0);
    sita2 = 360.0*m/60.0;
  }
  //cout << sita1 << endl;
  //cout << sita2 << endl;
  A = abs(sita1 - sita2)*acos(-1)/180;
  //cout << A << endl;
  cin >> a >> b >> h >> m;
  double ans = abs(sqrt(a*a+b*b-2*a*b*cos(A)));
    //cout << ans << endl;
  cout << fixed << setprecision(15) << ans << endl;
}

Measured memory_bytes: 4156
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int Q = sc.nextInt();
		Map<Integer, Integer> m = new HashMap<>();
		for(int i = 0; i < N-1; i++) {
			int a = sc.nextInt()-1;
			int b = sc.nextInt()-1;
			m.put(b, a);
		}
		int[] ans = new int[N];
		for(int i = 0; i < Q; i++) {
			int p = sc.nextInt()-1;
			int x = sc.nextInt();
			ans[p] += x;
		}
		for(int i = 1; i < N; i++)
			ans[i] += ans[m.get(i)];
		for(int i = 0; i < N; i++)
			System.out.print(ans[i] + " ");
		System.out.println();

	}

}

Measured memory_bytes: 189052
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    if a[i] % 2 == 0:
        if a[i] % 3 == 0 or a[i] % 5 == 0:
            continue
        else:
            print('DENIED')
            exit()
print('APPROVED')


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


BC_list = []
for i in range(M):
    b, c = map(int, input().split())
    BC_list.append((b, c))


BC_list = sorted(BC_list, reverse=True, key=lambda x: x[1])

c_ex = []
n = 0
for bc in BC_list:
    b, c = bc
    for i in range(b):
        c_ex.append(c)
    n += b
    if n >= N:
        break

A = A + c_ex
A = sorted(A, reverse=True)

s = sum(A[:N])
print(s)

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

using namespace std;

#define ll long long
#define pb push_back
#define mp make_pair
#define fst first
#define snd second

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

    int ans = 1e9;
    for(int i = 1; i <= 100; i++)
    {
        int total = 0;
        for(int j = 0; j < n; j++)
            total += pow(x[j] - i, 2);
        ans = min(ans, total);
    }

    cout << ans;

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

#define W -10
#define B -9
#define MAX 101
#define INF 20000000

void ISS(void);
void DA(void);

int n;/*頂点数*/
int T[MAX][MAX];/*行＝要素、列＝繋ってる要素*/
int color[MAX];/*色分け用配列*/
int d[MAX];
int pi[MAX];
int main()
{
  int i,j,youso,kazu,v,kyori;

  scanf("%d",&n);

  for(i=0;i<n;i++)
    {
      scanf("%d%d",&youso,&kazu);

      for(j=0;j<kazu;j++)
	{
	  scanf("%d%d",&v,&kyori);
	  T[i][v]=kyori;
	}
    }

  DA();

  for(i=0;i<n;i++)printf("%d %d\n",i,d[i]);
  
  return 0;
}

void ISS(void)
{
  int i;
  for(i=0;i<n;i++)
    {
      d[i]=INF;
      pi[i]=EOF;
      color[i]=W;
    }
  
  d[0]=0;
}

void DA(void)
{
  int i,j,k,min;

  ISS();

  while(1)
    {
      min=INF;
      for(i=0;i<n;i++)
	{
	  if(color[i]!=B && d[i]<min)
	    {
	      min=d[i];
	      j=i;
	    }
	}
      
      if(min==INF)
	{
	  break;
	}

      color[j]=B;

      for(k=0;k<n;k++)
	{
	  if(color[k]!=B && d[j]+T[j][k]<d[k]&&T[j][k]!=0)
	    {
	      pi[k]=j;
	      d[k]=d[j]+T[j][k];
	    }
	}
    }
}



Measured memory_bytes: 2108
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define fs first
#define se second
#define pi 2*acos(0)
#define PI 3.14159265358979323846264338

typedef long long ll;
typedef unsigned long long ull;
typedef pair < int , int > pii;
typedef pair < ll , ll > pll;

const int N = 100010;
const int MX = 123456;
const int mod = (int)1e9 + 7;
const int base = 1023456789;
const ull BS1 = 10000019ULL;
const int INF = (1 << 29);

template < class T > inline void fastScan(T &x){
    register char c = getchar();
    int neg = 0; x = 0;
    for(   ; (c < 48 || c > 57) && (c != '-'); c = getchar());
    if(c == '-') { neg = 1; c = getchar(); }
    for(   ; c > 47 && c < 58; c = getchar()){
        x = (x << 1) + (x << 3) + c - 48;
    }
    if(neg) x = -x;
}

// OrderedSet
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template < typename T > using ordered_set = tree < T, null_type, greater < T >, rb_tree_tag, tree_order_statistics_node_update >;

int main(){
  int a, b, c;
  fastScan(a);
  fastScan(b);
  fastScan(c);
  puts(a == b && b == c ? "Yes" : "No");
}


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

using namespace std;

string a , b ;
long long n , m ;
const long long N = 3e3 + 10 ;
long long dp[N][N] ;
long long dfs(long long x, long long y){
    if ( x >= n ) return 0 ;
    if ( y >= m ) return 0 ;
    if ( dp[x][y] != -1 ) return dp[x][y] ;
    long long choice1 = 0 ;
    long long choice2 = 0 ;
    long long choice3 = 0 ;
    if ( a[x] == b[y] ){
        choice1 = 1 + dfs(x + 1, y + 1) ;
    }
    else {
        choice2 = dfs(x + 1, y) ;
        choice3 = dfs(x, y + 1) ;
    }
    return dp[x][y] = max({choice1, choice2, choice3});
}
string ans = "" ;
void build(long long x, long long y){
    if ( x >= n ) return ;
    if ( y >= m ) return ;
    //if ( dp[x][y] != -1 ) return dp[x][y] ;
    long long choice1 = 0 ;
    long long choice2 = 0 ;
    long long choice3 = 0 ;
    if ( a[x] == b[y] ){
        choice1 = 1 + dfs(x + 1, y + 1) ;
    }
    else {
        choice2 = dfs(x + 1, y) ;
        choice3 = dfs(x, y + 1) ;
    }
    long long optimal = dfs(x, y) ;

    if ( optimal == choice2 ){

        build(x + 1, y) ;
    }
    else if ( optimal == choice3 ) {

        build(x, y + 1) ;
    }
    else if (optimal == choice1 ){
        ans += a[x];
        build(x + 1, y + 1) ;
    }

}
int main(){
    ios_base::sync_with_stdio(false) ;
    cin.tie(0) ;
    cout.tie(0) ;
    memset(dp, -1, sizeof dp) ;
    cin >> a >> b ;
    n = (long long) a.size() ;
    m = (long long) b.size() ;
    dfs(0, 0) ;
    build(0, 0) ;
    cout << ans << endl;
    return 0 ;
}


Measured memory_bytes: 71296
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define pb push_back
#define pii pair<int , int>
#define fast ios_base::sync_with_stdio(0)
#define mx 100005
#define mod 1000000007
ll dp[mx][2];
vi adj[mx];
/// 0 white, 1 black
ll fun(int p, int u, int color)
{
    ll& ret = dp[u][color];
    if(ret!=-1) return ret;
    ret = 1;
    for(int i=0; i<adj[u].size(); i++){
        int v = adj[u][i];
        if(v==p) continue;
        else{
            if(color==0)
                ret*=(fun(u,v,0) + fun(u,v,1));
            else
                ret*=fun(u,v,0);
            ret%=mod;
        }
    }
    return ret;
}
int main()
{
    fast;
    int n,a,b;
    cin>>n;
    for(int i=1; i<n; i++){
        cin>>a>>b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    memset(dp, -1, sizeof dp);
    cout<<(fun(-1, 1,0) +fun(-1, 1, 1))%mod<<endl;
}



Measured memory_bytes: 17024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const long long INF = 1e18;
# define len(x) ((int)(x).size())
# define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
# define reps(i, n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
# define rrep(i, n) for(int i=((int)(n)-1); i>=0; --i)
# define rreps(i, n) for(int i=((int)(n)); i>0; --i)
# define foreps(i, m, n) for(int i = m;i < n;i++)
# define ALL(x) (x).begin(), (x).end()
# define rall(x) (x).rbegin(), (x).rend()
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main() {
    ll N; cin >> N;
    vector<ll> A(N);
    map<ll, ll> mp;
    rep(i, N) {
        cin >> A[i]; mp[A[i]]++;
    }

    ll ans = 0;
    for (auto itr : mp) ans += itr.second * (itr.second - 1) / 2;
    rep(i, N) {
        ll val = mp[A[i]];
        ll before = val * (val - 1) / 2;
        ll after = (val - 1) * (val - 2) / 2;
        cout << ans - before + after << endl;
    }
}

Measured memory_bytes: 12688
MAX_SIZE = int(1e6) 


prime = [True] * (MAX_SIZE + 1) 

# coding seive
def seive(): 
	p = 2
	
	while (p * p <= MAX_SIZE): 
		
		if (prime[p] == True): 
			
		 for i in range(p * p, MAX_SIZE, p): 
				prime[i] = False
		p += 1

 
def Prime(n, k): 
	r = -1
	for i in range(n , MAX_SIZE): 
		
		
		if (prime[i] == True): 
			k -= 1
		
		if (k == 0): 
			r = i 
			break
	
	return r 
 
if __name__=='__main__': 
	n = int(input())
	k = 1
	seive() 
	
	
	print(Prime(n, k)) 
	

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

namespace ABC173_D
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            long[] A = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
            Array.Sort(A);
            Array.Reverse(A);

            Queue<long> queue = new Queue<long>();
            queue.Enqueue(A[0]);
            long sum = 0;

            for (int i = 1; i < N; i++)
            {
                sum += queue.Dequeue();
                queue.Enqueue(A[i]);
                queue.Enqueue(A[i]);
            }

            Console.WriteLine(sum);
        }
    }
}


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

#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ALL(a) (a).begin(),(a).end()
#define Yes(hoge) cout<<((hoge)?"Yes":"No")<<endl;
#define YES(hoge) cout<<((hoge)?"YES":"NO")<<endl;
using namespace std;
struct Grid{int x,y,t;};
struct Edge{int to,cost;};
struct Graph{vector<vector<Edge>>E;int V;
  const ll Inf = llINF;const int MAX_V=1010;vector<ll>d;
  Graph(int n):E(n){d.resize(MAX_V);E.resize(n);V=n;}
  void init(){for(int i=0;i<MAX_V;i++)d[i]=Inf;}
  void add_edge(int from,int to,int cost){E[from-1].pb({to-1,cost});}
};
int main(){
  int n;cin>>n;
  int k;
  cin>>k;
  ll dp[n+2000]={};
  for(int i=0;i<n+2000;i++)dp[i]=llINF;

  dp[0]=0;
  vector<ll>h(n+100);
  for(int i=0;i<n;i++)cin>>h[i];
  for(int i=0;i<n;i++){
    for(int j=1;j<=k;j++){
      dp[i+j]=min(dp[i+j],dp[i]+abs(h[i]-h[i+j]));
    }
  }
  //for(int i=0;i<=n;i++)cout<<dp[i]<<endl;
  cout<<dp[n-1]<<endl;
  return 0;
}


Measured memory_bytes: 1792
#dpは拡張されたdpテーブルでdp[i][j]はi日目にjの活動を選択したときに取れる最大の満足度
n = int(input())
dp = [[0]*3]*(n)
an = list(map(int,input().split()))
dp[0] = an
for i in range(1,n):
    
    a,b,c = list(map(int, input().split()))
    
    
    a_m = max(dp[i-1][1]+a, dp[i-1][2]+a)
    b_m = max(dp[i-1][0]+b, dp[i-1][2]+b)
    c_m = max(dp[i-1][0]+c, dp[i-1][1]+c) 
    dp[i] = [a_m,b_m,c_m]

print(max(dp[-1][:]))

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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

using i64=int64_t;

//10 1 2 3 4 5 6 7 8 9

vector<i64> unroll(i64 m,vector<i64> a){
    vector<i64> res={a.front()};

    i64 s=a.front();
    rep(i,1,a.size()){
        if(a[i]>a[i-1]){
            res.push_back(s+a[i]-a[i-1]);
            s+=a[i]-a[i-1];
        }else{
            res.push_back(s+m-a[i-1]+a[i]);
            s+=m-a[i-1]+a[i];
        }
    }
    return res;
}

void solve(){
    i64 n,m;
    cin >> n >> m;
    vector<i64> a(n);
    rep(i,0,n){
        cin >> a[i];
        --a[i];
    }

    auto a_=unroll(m,a);

    vector<queue<i64>> push(m);
    vector<i64> pop(a_.size()-1);
    vector<i64> d(a_.size()-1);
    rep(i,0,a_.size()-1){
        if(a_[i]<a_[i+1]){
            if(a_[i+1]-a_[i]<=1) continue;
            push[(a_[i]+2)%m].push(i);
            pop[i]=(a_[i+1]+1)%m;
            d[i]=a_[i+1]-a_[i]-1;
        }else{
            if(a_[i+1]+m-a_[i]<=1) continue;
            push[(a_[i]+2)%m].push(i);
            pop[i]=(a_[i+1]+1)%m;
            d[i]=a_[i+1]+m-a_[i]-1;
        }
    }

    i64 ans=0,s=0;
    rep(i,0,a.size()-1){
        if(a[i]<a[i+1]) s+=a[i+1]-a[i];
        else s+=m-a[i]+a[i+1];
    }
    ans=s;

    vector<i64> k(m);
    vector<vector<i64>> erase_id(m);
    i64 c=0,cnt_id=0;
    rep(i_,0,2*m){
        i64 i=i_%m;
        while(!push[i].empty()){
            ++cnt_id;
            erase_id[pop[push[i].front()]].push_back(push[i].front());
            push[i].pop();
        }

        for(auto id:erase_id[i]){
            --cnt_id;
            c-=d[id];
        }
        erase_id[i].clear();

        c+=cnt_id;
        k[i]+=c;
        ans=min(ans,s-k[i]);
    }
    cout << ans << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}


Measured memory_bytes: 76004
S = input()
T = input()
s = len(S)
t = len(T)
#A=[0]*(len(S))
 
ans = t
for i in range(len(S)-len(T)+1):
  x = 0
  for j in range(len(T)):
    if S[i+j] != T[j]:
      x += 1
  ans = min(ans, x)
 
#print(s)
#print(t)
#print(A)
print(ans)

Measured memory_bytes: 9064
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#define MOD 1000000007
#define mkp make_pair
typedef long long ll;
using namespace std;

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

  int ans=N/(2*D+1);
  if(N%(2*D+1)) ans++;
  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main()
{
	int i = 0;
	char password[20];
	int check = 0b0000;
	int strlength = 0;
	
	scanf("%s", password);
	
	do{
		if(password[i]>='0'&&password[i]<='9')	check |= 0b0001;
		if(password[i]>='a'&&password[i]<='z')	check |= 0b0010;
		if(password[i]>='A'&&password[i]<='Z')	check |= 0b0100;
		i++;
	}while(password[i] != '\0');
	
	if(i >= 6)	check |= 0b1000;
	
	if(check == 0b1111)	printf("VALID\n");
	else				printf("INVALID\n");
	
	return 0;
}

Measured memory_bytes: 524
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int num[N];
int main(){
	int n,q,x,b,c;scanf("%d",&n);long long sum=0;
	for(int i=0;i<n;i++)scanf("%d",&x),num[x]++,sum+=x;
	scanf("%d",&q);
	for(int i=0;i<q;i++){
		scanf("%d%d",&b,&c);
		sum+=1ll*(c-b)*num[b];
		num[c]+=num[b];num[b]=0;
		printf("%lld\n",sum);
	}
	return 0;
} 

Measured memory_bytes: 4200
#include <bits/stdc++.h>
#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 namespace std;

int main() {
   int a,b,c;
   cin >> a >> b >> c;
   cout << a*b/2 << endl; 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//For ordered_set
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define MOD 1000000007
#define test int t; cin>>t; while(t--)
#define init(arr,val) memset(arr,val,sizeof(arr))
#define loop(i,a,b) for(int i=a;i<b;i++)
#define loopr(i,a,b) for(int i=a;i>=b;i--)
#define loops(i,a,b,step) for(int i=a;i<b;i+=step)
#define looprs(i,a,b,step) for(int i=a;i>=b;i-=step)
#define ull unsigned long long int
#define ll long long int
#define P pair
#define PLL pair<long long, long long>
#define PII pair<int, int>
#define PUU pair<unsigned long long int, unsigned long long int>
#define L list
#define V vector
#define D deque
#define ST set
#define MS multiset
#define M map
#define UM unordered_map
#define mp make_pair
#define pb push_back
#define pf push_front
#define MM multimap
#define F first
#define S second
#define IT iterator
#define RIT reverse_iterator
#define FAST ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define FILE_READ_IN freopen("input.txt","r",stdin);
#define FILE_READ_OUT freopen("output.txt","w",stdout);
#define all(a) a.begin(),a.end()
#define ld long double
using namespace std;
// For ordered_set
using namespace __gnu_pbds;
template <typename T>
using ord_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll maxn = 1e5;
const ll inf = 1e9;
const double pi = acos(-1);

int main(){
    ll n;
    cin>>n;
    ll V[n];
    ll sum = 0;
    loop(i,0,n){
        cin>>V[i];
        sum+=V[i];
    }
    ll cache[3005][3005];
    init(cache,0);
    loopr(i,n,1){
        loop(j,1,n+1){
            if(i>j){
                continue;
            }
            if(i==j){
                cache[i][j] = V[i-1];
            }
            cache[i][j] = max(V[i-1]+min(cache[i+2][j], cache[i+1][j-1]), V[j-1] + min(cache[i][j-2],cache[i+1][j-1]));
        }
    }
    cout<<2*cache[1][n]-sum<<endl;
    return 0;
}

Measured memory_bytes: 70784
# coding: utf-8
import queue
 
class Node:
    def __init__(self, myNum, left, right):
        self.myNum = myNum
        self.left = left
        self.right = right
        self.parent = -1
        self.bs = -1
        self.nodeType = ""
        self.degree = -1
        self.depth = -1
        self.height = -1
 
         
nodes = []
n = int(input().rstrip())
for i in range(n):
    line = [int(j) for j in input().rstrip().split()]
    nodes.append(Node(line[0],line[1],line[2]))
 
nodes = sorted(nodes, key = lambda x: x.myNum)
 
# 親ノード、degreeを設定する
for node in nodes:
    dg = 0
    if node.left != -1:
        nodes[node.left].parent = node.myNum
        dg += 1
    if node.right != -1:
        nodes[node.right].parent = node.myNum
        dg += 1
    node.degree = dg
 
# 兄弟ノードを設定する
for node in nodes:
    if node.left != -1 and node.right != -1:
        nodes[node.left].bs = nodes[node.right].myNum
        nodes[node.right].bs = nodes[node.left].myNum
 
# nodeTypeを設定する
for node in nodes:
    if node.parent == -1:
        node.nodeType = "root"
        node.depth = 0
        rootNum = node.myNum
    elif node.left == -1 and node.right == -1:
        node.nodeType = "leaf"
    else:
        node.nodeType = "internal node"
 
# depthを設定する
q = queue.Queue()
q.put(nodes[rootNum])
while not q.empty():
    nd = q.get()
    if nd.left != -1:
        nodes[nd.left].depth = nd.depth + 1
        q.put(nodes[nd.left])
    if nd.right != -1:
        nodes[nd.right].depth = nd.depth + 1
        q.put(nodes[nd.right])
 
# heightを設定する
for node in nodes:
    if node.parent == -1 or node.nodeType == "leaf":
        node.height = 0
        q.put(node)
while not q.empty():
    nd = q.get()
    if nd.parent != -1:
        nodes[nd.parent].height = max(nodes[nd.parent].height, nd.height + 1)
        q.put(nodes[nd.parent])

# Preorder
def dfsPreorder(x):
    if nodes[x].height == 0:
        print(" " + str(x),end="")
        return
    
    print(" " + str(nodes[x].myNum),end="")
    if nodes[x].left != -1:
        dfsPreorder(nodes[x].left)
    if nodes[x].right != -1:
        dfsPreorder(nodes[x].right)

# Inorder
def dfsInorder(x):
    if nodes[x].height == 0:
        print(" " + str(x),end="")
        return
    
    if nodes[x].left != -1:
        dfsInorder(nodes[x].left)
    print(" " + str(nodes[x].myNum),end="")
    if nodes[x].right != -1:
        dfsInorder(nodes[x].right)
    
# Postorder
def dfsPostorder(x):
    if nodes[x].height == 0:
        print(" " + str(x),end="")
        return
    
    if nodes[x].left != -1:
        dfsPostorder(nodes[x].left)
    if nodes[x].right != -1:
        dfsPostorder(nodes[x].right)
    print(" " + str(nodes[x].myNum),end="")

print("Preorder")
dfsPreorder(rootNum)
print()
print("Inorder")
dfsInorder(rootNum)
print()
print("Postorder")
dfsPostorder(rootNum)
print()


Measured memory_bytes: 6872
// finish date: 2018/12/21

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int (i)=a;(i)<(b);(i)++)
#define rep(i, n)  FOR(i,0,n)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>>
        vvvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<double> vd;
typedef vector<vector<double>> vvd;
typedef vector<vector<vector<double>>> vvvd;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, pair<int, int>> plii;
const int bigmod = 1000000007;
const int INF = 1050000000;
const long long INFll = 100000000000000000;


int main() {
    //入力と変数宣言
    int H, W, N;
    cin >> H >> W >> N;
    vi X(N), Y(N);
    rep(i, N) {
        cin >> X[i] >> Y[i];
        X[i]--;
        Y[i]--;
    }
    set<pii> block;
    rep(i, N) block.insert(pii(X[i], Y[i]));
    //rep(i, H) block.insert(pii(i, W));
    rep(i, W) block.insert(pii(H, i));
    vi move(W, INT_MAX);
    move[0] = 0;

    int x = 0, y = 0;
    while (x < H && y < W) {
        if (block.find(pii(x + 1, y)) == block.end()) {
            x += 1;
            move[y] = x;
            if (block.find(pii(x, y + 1)) == block.end()) {
                y += 1;
            }
        } else {
            move[y] = x;
            break;
        }
    }

    int ans = INT_MAX;
    for (auto b:block) {
        if (move[b.second] < b.first) {
            ans = min(ans, b.first);
        }
    }
    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 21376
#include<stdio.h>
#include <stdlib.h>



int main() {
	int a, b;
	scanf("%d%d", &a, &b);
	if (a < 10 && b < 10) {
		printf("%d\n", a*b);
	}
	else {
		printf("-1\n");
	}
	return 0;
}

Measured memory_bytes: 128
// AOJ 2275: Fox Number
// 2017.12.11 bal4u@uu

#include <stdio.h>
#include <string.h>
#include <math.h>

#define MAX  707106			// sqrt(10^12/2)
char tbl[MAX+1];

int sz;						// max sz = 57084, prime[0] = 2, prime[57083] = 707099
int prime[57100] = {  		// prime[146] = 853, prime[147] = 857
  2, 3,  5,  7, 11, 13, 17, 19, 23, 29, 
 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 
 73, 79, 83, 89, 97,101,103,107,109,113, 
127,131,137,139,149,151,157,163,167,173,
179,181,191,193,197,199,211,223,227,229, 
233,239,241,251,257,263,269,271,277,281, 
283,293,307,311,313,317,331,337,347,349, 
353,359,367,373,379,383,389,397,401,409, 
419,421,431,433,439,443,449,457,461,463, 
467,479,487,491,499,503,509,521,523,541, 
547,557,563,569,571,577,587,593,599,601, 
607,613,617,619,631,641,643,647,653,659, 
661,673,677,683,691,701,709,719,727,733, 
739,743,751,757,761,769,773,787,797,809, 
811,821,823,827,829,839,853 };

void sieve()
{
	int i, j, k;

	for (i = 1; i < 147; i++) {
		k = prime[i];
		for (j = k*k; j < MAX; j += k) tbl[j] = 1;
	}
	for (sz = 146, i = 853; i <= MAX; i += 2) if (!tbl[i]) prime[sz++] = i;
//	printf("sz %d, prime[%d]=%d\n", sz, sz-1, prime[sz-1]);
//	        sz 57084, prime[57083]=707099
}

int base[1000002];
int idx [1000002];
long long pp[41];		// 2^40 = 1099511627776 >= 10^12

int bsch(int x)
{
	int m, l = 0, r = sz;

    while (l < r) {
        m = (l + r) >> 1;
		if (prime[m] == x) return m;
        if (prime[m] < x) l = m + 1; else r = m;
    }
	return l-1;
}

int main()
{
	int i, k, p, ans;
	long long A, B, a, b, j, n;

	sieve();

	scanf("%lld%lld", &A, &B);
	a = A-B, b = A+B;
	if (b <= 1) { puts("0"); return 0; }
	if (a <= 1) a = 2;

	sz = bsch((int)sqrt((double)(b >> 1)));

	memset(idx, 1, sizeof(idx));
	for (i = 0; i <= sz; i++) {
		p = prime[i];
		k = 1; for (j = p; j <= b; j *= p) pp[k++] = j;
		while (--k) {
			j = pp[k], n = j*(1+(a-1)/j);
			for (; n <= b; n += j) {
				int x = (int)(n-a);
				if (!idx[x] || base[x] == p) continue;
				if (idx[x] < k) idx[x] = 0;
				else base[x] = p, idx[x] = k;
			}
		}
	}

	ans = 0, i = (int)(b-a+1); while (i--) if (idx[i]) ans++;
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 10508
N,M,C = list(map(int,input().split()))

B = list(map(int,input().split()))

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

point = 0
count = 0
for i in range(N):
	for j in range(M):
		point += (A[i][j] * B[j])
	if point + C > 0:
		count += 1
	point = 0

print(count)

Measured memory_bytes: 3064
open System
let n = stdin.ReadLine() |> int

let mutable arr = [|[|0;0;0;0;0;0;0;0;0;0|];[|0;0;0;0;0;0;0;0;0;0|];[|0;0;0;0;0;0;0;0;0;0|];[|0;0;0;0;0;0;0;0;0;0|];[|0;0;0;0;0;0;0;0;0;0|];[|0;0;0;0;0;0;0;0;0;0|];[|0;0;0;0;0;0;0;0;0;0|];[|0;0;0;0;0;0;0;0;0;0|];[|0;0;0;0;0;0;0;0;0;0|];[|0;0;0;0;0;0;0;0;0;0|]|]

let f (x:int) = let keta = int(Math.Log10(float x))
                let keta_10 = int(10.0 ** (float keta))
                x / keta_10

let g (x:int) = x % 10

for i in 1..n do
 let hd = f i
 let tl = g i
 arr.[hd].[tl] <- (arr.[hd].[tl] + 1)

let ans1 = [for i in 1..9 -> arr.[i].[i]] |> List.sumBy (fun x -> (x * x))
let ans2 = [for i in 1..8 do
            for j in (i + 1)..9 -> (arr.[i].[j] * arr.[j].[i] * 2)] |> List.sum

(ans1 + ans2)
|>stdout.WriteLine

Measured memory_bytes: 13524
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)  
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define RVSORT(v) sort(v.rbegin(), v.rend());
#define ll long long
#define pb(a) push_back(a)
#define INF 999999999
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

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

int gcd(int a,int b){return b?gcd(b,a%b):a;}

ll modpow(ll n,ll k){
  if(k == 1){
    return n;
  }else if(k == 0){
    return 1;
  }else if(k%2==0){
    ll memo = modpow(n,k/2)%MOD;
    return memo*memo%MOD;
  }else{
    return n * modpow(n,k-1)%MOD;
  }
}

int main(){

  int n;cin>>n;
  double d[n];
  REP(i,n){
    cin>>d[i];
  }
 
  double sum = 0;
  REP(i,n){
    sum += 1/d[i];
  }

  cout<<setprecision(12)<<1/sum<<endl;


  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>

char moji(char x){
  if(x=='T') x='a';
  if(x=='L') x='i';
  if(x=='U') x='u';
  if(x=='R') x='e';
  if(x=='D') x='o';
  return x;
}


int main(){
  char a[1000],b[1000];
  int i,j,len,t=0;


    scanf("%s",a);
  
  len=strlen(a);

  for(i=0;i<len;i++){
    if(a[i]=='0'){
        if(a[i+1]!='U' && a[i+1]!='L' && a[i+1]!='R'){
      b[t]='w';
      t++;
      b[t]=moji(a[i+1]);
      t++;
      }
	
      if(a[i+1]=='U'){
	b[t]='n';
	t++;
	b[t]='n';
	t++;
      }
    }
    else if(a[i]=='1'){
      b[t]=moji(a[i+1]);
      t++;
    }

    else if(a[i]=='2'){
	b[t]='k';
	t++;
	b[t]=moji(a[i+1]);
	t++;
      }
    else if(a[i]=='3'){
      b[t]='s';
      t++;
	b[t]=moji(a[i+1]);
      t++;
    }

    else if(a[i]=='4'){
      b[t]='t';
      t++;
      b[t]=moji(a[i+1]);
      t++;
    }
    else if(a[i]=='5'){
      b[t]='n';
      t++;
      b[t]=moji(a[i+1]);
      t++;
    }
    else if(a[i]=='6'){
      b[t]='h';
      t++;
      b[t]=moji(a[i+1]);
      t++;
      
    }
    else if(a[i]=='7'){
      b[t]='m';
      t++;
      b[t]=moji(a[i+1]);
      t++;
    }
    else if(a[i]=='8'){
      if(a[i+1]!='L' && a[i+1]!='R'){
      b[t]='y';
      t++;
      b[t]=moji(a[i+1]);
      t++;
      }
    }

    else if(a[i]=='9'){
      b[t]='r';
      t++;
      b[t]=moji(a[i+1]);
      t++;
    }
  }
  for(i=0;i<t;i++){
    printf("%c",b[i]);
  }
  printf("\n");

  return 0;
}

    

Measured memory_bytes: 524
#include <bits/stdc++.h>
#define lli long long int
#define MOD 1000000007
#define INF INT_MAX // 2147483647
#define INFLL LLONG_MAX // 9223372036854775807
#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define repf(i, n) for(int i=1; i<(int)(n+1); i++)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<lli>
#define vvi vector<vector<lli>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(10);
    int n;
    string s;
    cin >> n >> s;
    rep(i, s.size()){
        if(s.at(i)+n >=91){
            s.at(i) = (char)((s.at(i)+n)%91+65);
        }
        else s.at(i) = (char)(s.at(i)+n);
    }
    cout << s << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <ctype.h>


int main(void)
{	
	int c;
	while((c=getchar())!=EOF){
		if(isalpha(c)){
			printf("%c",toupper(c));
		}
		else{
			printf("%c",c);
		}
	}
	return 0;
}

Measured memory_bytes: 0
#include<stdio.h>

int main(void){
    int N=0;
    long A[200000]={0};
    long B[200000]={0};
    // long S[200000]={0};
    long sum=0;
    long count=0;
    scanf("%d",&N);
    for(int i=0;i<N+1;i++){
        scanf("%ld",&A[i]);
        /* if(i>0){
            S[i]=S[i-1]+A[i];
        }
        else{
            S[i]=A[i];
            }*/
        sum+=A[i];
    }
    for(int i=0;i<N;i++){
        scanf("%ld",&B[i]);
        if(A[i]<B[i]){
            int temp=A[i]+A[i+1];
            A[i+1]=A[i+1]-B[i]+A[i];
            if(A[i+1]<0){
                A[i+1]=0;
                count+=temp;
            }
            else count+=B[i];
        }
        else{
            count+=B[i];
        }
        
    }
    if(A[N+1]<0){
        count+=A[N+1];
    }
    printf("%ld\n",count);
    return 0;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
#define ri register int
namespace io {
	const int SIZE = (1 << 21) + 1;
	char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
	// getchar
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	// print the remaining part
	inline void flush () {
		fwrite (obuf, 1, oS - obuf, stdout);
		oS = obuf;
	}
	// putchar
	inline void putc (char x) {
		*oS ++ = x;
		if (oS == oT) flush ();
	}
	// input a signed integer
	template <class I>
	inline void gi (I &x) {
		for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
		for (x = 0; c <= '9' && c >= '0'; c = gc()) x = (x << 1) + (x << 3) + (c & 15); x *= f;
	}
	// input a letter
	template <class I>
	inline void get (I &x) {
		for (c = gc(); c < 'A' || c > 'Z'; c = gc()) ;
		x = c;
	}
	// input a string
	inline void read (char *s){
		for(c = gc(); c < 'A' || c > 'Z'; c = gc()) ;
		for(; c >= 'A' && c <= 'Z'; c = gc()) *++s = c;
		*++s = '\0';
	}
	// print a signed integer
	template <class I>
	inline void print (I x) {
		if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
		while (x) qu[++ qr] = x % 10 + '0',  x /= 10;
		while (qr) putc (qu[qr --]);
	}
	//no need to call flush at the end manually!
	struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: gi;
using io :: get;
using io :: read;
using io :: putc;
using io :: print;
const int N=3e5+5;
int a[N],tag[N],tag0[N],tag1[N];
int main(){
	ri n,i,j,l,r,k,lstl,lstr;
	gi(n);
	for(i=1;i<=n;++i){ 
		gi(a[i]);
		if(a[i]!=i){
			if((a[i]&1)!=(i&1)) return puts("No"),0;
			if(a[i]<i){
				if(i&1)
					++tag0[a[i]+1],
					--tag0[i];
				else
					++tag1[a[i]+1],
					--tag1[i];
			}
			else{
				if(i&1)
					++tag0[i+1],
					--tag0[a[i]];
				else
					++tag1[i+1],
					--tag1[a[i]];
			}
		} 
	}
	 
	for(i=1;i<=n;++i){
		tag0[i]+=tag0[i-1];
		tag1[i]+=tag1[i-1];
		if(i&1)
			tag[i]=tag1[i];
		else
			tag[i]=tag0[i];
		if(tag[i]&&tag[i-1])
			return puts("No"),0;
	}
	for(i=1;i<=n;++i){
		if(!tag[i]) continue;
		for(j=i;j<=n;++j)
			if(tag[j]&&!tag[j+1]&&!tag[j+2])
				break;
		l=max(1,i-1);r=min(n,j+1);
		for(k=l;k<=r;++k)
			if(a[k]<l||a[k]>r)
				return puts("No"),0;
		for(k=l;k<=r;++k)
			if(k-2>=l&&(a[k]==k)^(a[k-2]==k-2))
				return puts("No"),0;
		lstl=lstr=0;
		for(k=l;k<=r;++k)
			if(a[k]!=k){
				if(a[k]<k){
				//	printf("lstl %d %d\n",lstl,a[k]);
					if(lstl>a[k]) return puts("No"),0;
					lstl=a[k]; 
				} 
				else{
				//	printf("lstr %d %d\n",lstr,a[k]);
					if(lstr>a[k]) return puts("No"),0;
					lstr=a[k];
				}
			}
		i=j;
	}
	puts("Yes");
	return 0;
}

Measured memory_bytes: 8960
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdint.h>
#include<stdbool.h>
#include<tgmath.h>
#include<time.h>
#define ll long long
#define min(a,b) ((a)>(b)?(b):(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define miin(a,b,c) min((a), min((b), (c)))
#define maax(a,b,c) max((a), max((b), (c)))

int a, b;

int main(){
    scanf("%d%d", &a, &b);
    printf("%d\n", b + (a<10?1000-100*a:0));
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#define  ms(a,b) memset(a,b,sizeof(a))

using namespace std;
typedef long long LL;
const LL INF=1e17L;
const int inf=0x3f3f3f3f;
const int maxn=1e5+5;
const int Mod=1e9+7;
int n,dp[10005],a[105];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    ms(dp,0);
    dp[0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=10000;j>=a[i];j--)
        {
            if(dp[j-a[i]]) dp[j]=1;
        }
    }
    int ans=0;
    for(int i=10000;i>=1;i--)
    {
        if(dp[i] && i%10!=0)
        {
            ans=i;break;
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
from sys import stdin
def main():
    N, M = map(int, stdin.readline().rstrip().split())
    Lmax = 1
    Rmin = N
    for i in range(M):
      L, R = map(int, stdin.readline().rstrip().split())
      if Lmax < L:
        Lmax = L
      if Rmin > R:
        Rmin = R
    if Rmin - Lmax < 0:
      print(0)
    else:
      print(Rmin - Lmax + 1)

input = lambda: stdin.readline()
main()


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

using namespace std;

using u128 = __uint128_t;

#define int long long
#define mod 1000000007

char x[25][25];

bool visited[25][25];
int d[25][25];
int maxi = -1;
void select(){
    for (int i = 0; i < 25; ++i) {
        for (int j = 0; j < 25; ++j) {
            if(maxi < d[i][j]){
                maxi = d[i][j];
            }
        }
    }
}
void find_max(int i, int j, int n, int m){
    queue<pair<int, int> > q;
    q.push({i, j});
    visited[i][j] = true;
    d[i][j] = 0;
    while(!q.empty()){
        int ii = q.front().first , jj= q.front().second;
        q.pop();
        // left
        if(jj -1 >= 0 && x[ii][jj-1] != '#' && !visited[ii][jj-1]){
            visited[ii][jj-1] = true;
            d[ii][jj-1] = d[ii][jj] + 1;
            q.push({ii, jj-1});
        }
        if(jj +1 < m && x[ii][jj+1] != '#' && !visited[ii][jj+1]){
            visited[ii][jj+1] = true;
            d[ii][jj+1] = d[ii][jj] + 1;
            q.push({ii, jj+1});
        }
        if(ii - 1 >= 0 && x[ii-1][jj] != '#' && !visited[ii-1][jj]){
            visited[ii-1][jj] = true;
            d[ii-1][jj] = d[ii][jj] + 1;
            q.push({ii-1, jj});
        }
        if(ii + 1 <  n && x[ii+1][jj] != '#' && !visited[ii+1][jj]){
            visited[ii+1][jj] = true;
            d[ii+1][jj] = d[ii][jj] + 1;
            q.push({ii+1, jj});
        }

    }
}
int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin>>n>>m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin>>x[i][j];
        }
    }
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < m; ++i) {
            if(x[k][i] == '#') continue;
            memset(visited, false, sizeof(visited));
            memset(d, -1, sizeof(d));
            find_max(k, i, n, m);
            select();
        }
    }
    cout<<maxi<<endl;
    return 0;
}

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

int main(){
    int N,X;
    cin>>N>>X;
    vector<int> p(N);

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

    sort(p.begin(),p.end());

    int count = N;

    while(X >= p[0]){
        X -=p[0];
        count++;
    }

    cout<<count<<endl;

}

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

mt19937 mt(time(nullptr));
// uniform_int_distribution< int > rand_int(0, 10) // rand[0, 10] inclusive

int main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed;
  string s;
  cin >> s;
  cout << (s[0]==s[1] || s[1]==s[2] || s[2]==s[3] ? "Bad" : "Good") << endl;
  return 0;
}


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

int main() {
  long n, k;
  std::cin >> n >> k;

  n = n % k;
  if (n == 0)
    std::cout << n << std::endl;
  else if (std::abs(n - k) < n)                                                 
    std::cout << std::abs(n - k) << std::endl;
  else
    std::cout << n << std::endl;
}

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

int main() {
  int64_t n;
  cin>>n;
  vector<int64_t> a(n);
  vector<int64_t> A(n);
  vector<int64_t> ans(n-1);
  for(int64_t i=0;i<n;i++){
    cin>>a.at(i);
  }
  A.at(0)=a.at(0);
  for(int i=1;i<n;i++){
   A.at(i)=A.at(i-1)+a.at(i);
  }
  for(int i=0;i<n-1;i++){
   ans.at(i)=abs(A.at(i)-(A.at(n-1)-A.at(i)));
  }
  sort(ans.begin(),ans.end());
  cout<<ans.at(0)<<endl;
}

Measured memory_bytes: 4992
import java.util.Scanner;

/**
 *
 * @author German le yo
 */
public class Main{
    
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        
        int N = scan.nextInt();
        int[] state = new int[N];
        int[] stones = new int[N];
        
        scan.nextLine();
        String[] input = scan.nextLine().split(" ");
        
        for(int i = 0; i < N; i++) stones[i] = Integer.parseInt(input[i]);
        
        state[0] = 0;
        state[1] = Math.abs(stones[0] - stones[1]);
        
        for(int i = 2; i < N; i++)
            state[i] = Math.min(Math.abs(stones[i] - stones[i - 1]) + state[i - 1], Math.abs(stones[i] - stones[i - 2]) + state[i - 2]);
        
        System.out.println(state[N - 1]);
        scan.close();
    }
    
}


Measured memory_bytes: 36264