akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

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

using namespace std;

namespace mp = boost::multiprecision;
using Bint = mp::cpp_int;

using ll = long long;
ll mod = pow(10, 9) + 7;

template <typename T> void output(T, ll);
ll gcd(ll, ll);
ll lcm(ll, ll);
Bint comb(Bint, Bint);
void prime_map(map<ll, ll> &, ll);

int main() {
    // source
    int n;
    cin >> n;
    int a[n];
    rep(i, n) { cin >> a[i]; }
    double mother = 0;
    rep(i, n) { mother += (double)1 / a[i]; }

    double ans = (double)1 / mother;

    cout << ans << endl;
    return 0;
}

Bint comb(Bint a, Bint b) {
    Bint ans = 1;

    if (a < b) {
        return 0;
    }

    rep(i, b) {
        ans *= a - i;
        ans /= i + 1;
    }

    return ans;
}

template <typename T> void output(T a, int precision) {
    if (precision > 0) {
        cout << setprecision(precision) << a << "\n";
    } else {
        cout << a << "\n";
    }
}

template <typename T> T min(T a, T b) {

    if (a < b) {
        return a;
    } else {
        return b;
    }
}

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

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

void prime_map(map<ll, ll> &m, ll num) {
    ll cache = num;
    repd(i, 2, sqrt(num) + 2) {
        if (num % i == 0) {
            if (m[i] == 0) {
                m[i] = 1;
            } else {
                m[i]++;
            }

            num /= i;
            break;
        }
    }

    if (cache == num) {
        if (m[num] == 0) {
            m[num] = 1;
        } else {
            m[num]++;
        }
        return;
    } else {
        prime_map(m, num);
    }
}


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

using namespace std;
int main()
{
	vector<int> a(5);
	for (int i = 0; i < 5; i++)
	{
		cin >> a[i];
	}
	int min = 10;
	int index = -1;
	for (int i = 0; i < 5; i++)
	{
		if (a[i] % 10 < min && a[i] % 10 != 0) {
			min = a[i] % 10;
			index = i;
		}
	}
	int s = 0;
	for (int i = 0; i < 5; i++)
	{
		if (i != index && a[i] % 10 != 0)
			s += (a[i] / 10) * 10 + 10;
		else
			s += a[i];
	}
	cout << s << endl;
}



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

using namespace std;


int main(){
    bitset<64> status_bit(0);
    int num_query;
    int command,idx;
    scanf("%d",&num_query);

    for(int i = 0;i < num_query;i++){
        cin >> command;
        switch(command){
            case 0: // test
                cin >> idx;
                cout << status_bit.test(idx) << "\n";
                break;
            case 1: // set
                cin >> idx;
                status_bit.set(idx);
                break;
            case 2: // clear
                cin >> idx;
                status_bit.reset(idx);
                break;
            case 3: // flip
                cin >> idx;
                status_bit.flip(idx);
                break;
            case 4: //all
                cout << status_bit.all() << "\n";
                break;
            case 5: //any
                cout << status_bit.any() << "\n";
                break;
            case 6: //none
                cout << status_bit.none() << "\n";
                break;
            case 7: //count
                cout << status_bit.count() << "\n";
                break;
            case 8: // val
                cout << status_bit.to_ulong() << "\n";
                break;
        }
    }
    return 0;   
}



Measured memory_bytes: 3168
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp(x) fixed << setprecision(x)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const ll MOD = 1000000007;
//const ll MOD = 998244353;
const int inf = (1<<30)-1;
const ll INF = (1LL<<60)-1;
const double pi = acos(-1.0);
const double EPS = 1e-10;
template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};
template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};

struct Union_Find_Tree{
    vector<int> par, rank, num;
    
    Union_Find_Tree(int N){
        par.assign(N, -1);
        rank.assign(N, 0);
        num.assign(N, 1);
    }
    
    int root(int x){
        if(par[x] < 0 || par[x] == x) return x;
        return par[x] = root(par[x]);
    }
    
    bool unite(int x, int y){
        x = root(x), y = root(y);
        if(x == y) return false;
        if(rank[x] < rank[y]) swap(x, y);
        if(rank[x] == rank[y]) rank[x]++;
        par[y] = x, num[x] += num[y];
        return true;
    }
    
    int size(int x) {return num[root(x)];}
    
    bool same(int x, int y){
        return root(x) == root(y);
    }
    
    void clear(){
        fill(par.begin(), par.end(), -1);
        fill(rank.begin(), rank.end(), 0);
        fill(num.begin(), num.end(), 1);
    }
};

int main(){
    int N, M;
    cin >> N >> M;
    Union_Find_Tree uf(N);
    rep(i, M){
        int u, v; cin >> u >> v; u--, v--;
        uf.unite(u, v);
    }
    int ans = 0;
    rep(i, N) chmax(ans, uf.size(i));
    cout << ans << endl;
}

Measured memory_bytes: 5552
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define Sort(x) sort((x).begin(), (x).end())
#define Reverse(x) reverse((x).begin(), (x).end())
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define INF INT_MAX
#define fcout cout << fixed << setprecision(15) //15桁まで表示
using str = string;
using ll = long long;
using ull = unsigned long long;
using ui = unsigned int;
using puu = pair<ui,ui>;
using P = pair<int, int>;
using vi = vector<int>;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int lcm(int a,int b){return a * b / gcd(a, b);};
int floor(int a,int b){return (a+b-1)/b;};
int month[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
template<class T>inline bool chmax(T& a,T b){if(a < b){a=b;return true;}return false;};
template<class T>inline bool chmin(T& a,T b){if(a > b){a=b;return true;}return false;};
const ll mod = 1000000007;
const double PI = acos(-1.0);
vector<long long> divisor(long long n) {
    vector<long long> ret;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    return ret;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(20) << setiosflags(ios::fixed);
  int n;
  cin >> n;
  vector<ll> a(n);
  rep(i,n) cin >> a[i];
  Sort(a);
  map<ll,ll> dic;
  rep(i,n){
    if (dic.count(a[i])){dic[a[i]]=0; continue;}
    bool f=1;
    vector<ll> x=divisor(a[i]);
    for(ll k:x){
      if(dic.count(k)){
        f=0;
        break;
      }
    }
    if (f) dic[a[i]]=1;
  }
  ll ans=0;
  for(auto p:dic) {ans+=p.second;}
  cout << ans << endl;
}

Measured memory_bytes: 17192
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string>
const long long mod = 1000000007;

int search(int *d, int t, int n) {
	int r = 0;
	for (int i = 20; i >= 0; i--) {
		int c = r + (1 << i);
		if (c >= n)continue;
		if (d[c] >= t)r = c;
	}
	if (r == 0) {
		if (d[0] >= t)return 1;
		else return 0;
	}
	else {
		return r + 1;
	}
}

int main() {
	int N;
	scanf("%d", &N);
	int *A = new int[N];
	for (int i = 0; i < N; i++) {
		scanf("%d", A + i);
	}
	std::vector<int> c;
	c.push_back(A[0]);
	for (int i = 1; i < N; i++) {
		int r = search(c.data(), A[i], c.size());
		if (r >= c.size()) {
			c.push_back(A[i]);
		}
		else {
			c[r] = A[i];
		}
	}
	printf("%d", c.size());
	return 0;
}

Measured memory_bytes: 1276
import java.util.*; import java.io.*; import java.math.*;
public class Main{
	//Don't have to see. start------------------------------------------
	static class InputIterator{
		ArrayList<String> inputLine = new ArrayList<String>(1024);
		int index = 0; int max; String read;
		InputIterator(){
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			try{
				while((read = br.readLine()) != null){
					inputLine.add(read);
				}
			}catch(IOException e){}
			max = inputLine.size();
		}
		boolean hasNext(){return (index < max);}
		String next(){
			if(hasNext()){
				return inputLine.get(index++);
			}else{
				throw new IndexOutOfBoundsException("There is no more input");
			}
		}
	}
	static HashMap<Integer, String> CONVSTR = new HashMap<Integer, String>();
	static InputIterator ii = new InputIterator();//This class cannot be used in reactive problem.
	static PrintWriter out = new PrintWriter(System.out);
	static void flush(){out.flush();}
	static void myout(Object t){out.println(t);}
	static void myerr(Object t){System.err.print("debug:");System.err.println(t);}
	static String next(){return ii.next();}
	static boolean hasNext(){return ii.hasNext();}
	static int nextInt(){return Integer.parseInt(next());}
	static long nextLong(){return Long.parseLong(next());}
	static double nextDouble(){return Double.parseDouble(next());}
	static ArrayList<String> nextStrArray(){return myconv(next(), 8);}
	static ArrayList<String> nextCharArray(){return myconv(next(), 0);}
	static ArrayList<Integer> nextIntArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Integer> ret = new ArrayList<Integer>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Integer.parseInt(input.get(i)));
		}
		return ret;
	}
	static ArrayList<Long> nextLongArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Long> ret = new ArrayList<Long>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Long.parseLong(input.get(i)));
		}
		return ret;
	}
	static String myconv(Object list, int no){//only join
		String joinString = CONVSTR.get(no);
		if(list instanceof String[]){
			return String.join(joinString, (String[])list);
		}else if(list instanceof ArrayList){
			return String.join(joinString, (ArrayList)list);
		}else{
			throw new ClassCastException("Don't join");
		}
	}
	static ArrayList<String> myconv(String str, int no){//only split
		String splitString = CONVSTR.get(no);
		return new ArrayList<String>(Arrays.asList(str.split(splitString)));
	}
	public static void main(String[] args){
		CONVSTR.put(8, " "); CONVSTR.put(9, "\n"); CONVSTR.put(0, "");
		solve();flush();
	}
	//Don't have to see. end------------------------------------------
	static void solve(){//Here is the main function
		ArrayList<Integer> one = nextIntArray();
		int s = one.get(0) * 100 + one.get(1) * 10 + one.get(2);
		if(s % 4 == 0){
			myout("YES");
		}else{
			myout("NO");
		}
	}
	//Method addition frame start



	//Method addition frame end
}


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

int main(){
    int a,b,c,d;
    cin >> a >> b >>c >> d;
    int i=1;
    while(1){
        if(i%2==1){
            c=c-b;
            if(c<=0){
                cout << "Yes" << endl;
                return 0;
            }
        }
        else{
            a=a-d;
            if(a<=0){
                cout << "No" << endl;
                return 0;
            }
        }
        i++;
    }
}

Measured memory_bytes: 3624
f = lambda x: sum(map(int, str(x)))

a, b = 1, 1
for i in range(int(input())):
	print(a)
	a += 1
	b = a
	for j in range(0, len(str(a)) + 1):
		t = a % 10 ** j
		t = a - t + 10 ** j - 1
		if b * f(t) > t * f(b):
			b = t
	a = b


Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <climits> 
int main(){
    long A,B;
    std::cin >> A >> B;
    std::cout << A*B << std::endl;
    return 0;
}


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

using namespace std;

int main() {
string n;
cin>>n;
long int to;
for( int i=0;i<n.size();i++)
{
int e=i;
char t=n[i];
int n=0;
 if(t=='0')n=0;
 if(t=='1')n=1;
 if(t=='2')n=2;
 if(t=='3')n=3; 
 if(t=='4')n=4;
 if(t=='5')n=5;
 if(t=='6')n=6;
 if(t=='7')n=7;
 if(t=='8')n=8;
 if(t=='9')n=9;
to=to+n;
 }
if(to%9==0)
{cout<<"Yes"<<endl;
}
else
{cout<<"No"<<endl;
}
}

Measured memory_bytes: 3708
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int n = sc.nextInt();
        DSU dsu = new DSU(n);
        int q = sc.nextInt();
        for(int i = 0; i < q; i++){
            int t = sc.nextInt();
            int a = sc.nextInt();
            int b = sc.nextInt();
            if(t == 0){
                dsu.merge(a, b);
            }else if(t == 1){
                if(dsu.same(a, b)){
                    pw.println(1);
                }else{
                    pw.println(0);
                }
            }
        }
        pw.close();
    }
}

class DSU{
    private int n;
    private int[] parentOrSize;
    
    public DSU(int n){
        this.n = n;
        this.parentOrSize = new int[n];
        Arrays.fill(parentOrSize,-1);
    }
    
    int merge(int a, int b){
        if(!(0 <= a && a < n) || !(0 <= b && b < n)){
            // この式が成立しない物は動作しません。
            return -1;
        }
        int x = leader(a);
        int y = leader(b);
        if(x == y) return x;
        if(-parentOrSize[x] < -parentOrSize[y]){
            int tmp = x;
            x = y;
            y = tmp;
        }
        parentOrSize[x] += parentOrSize[y];
        parentOrSize[y] = x;
        return x;
    }
    
    boolean same(int a, int b){
        if(!(0 <= a && a < n) || !(0 <= b && b < n)){
            // この式が成立しない物は動作しません。
            return false;
        }
        return leader(a) == leader(b);
    }
    
    int leader(int a){
        if (parentOrSize[a] < 0){
            return a;
        }else{
            parentOrSize[a] = leader(parentOrSize[a]);
            return parentOrSize[a];
        }
    }

    int size(int a) {
        if(!(0 <= a && a < n)){
            // この式が成立しない物は動作しません。
            return -1;
        }
        return -parentOrSize[leader(a)];
    }
    
    ArrayList<ArrayList<Integer>> groups(){
        int[] leaderBuf = new int[n];
        int[] groupSize = new int[n];
        for(int i = 0; i < n; i++){
            leaderBuf[i] = leader(i);
            groupSize[leaderBuf[i]]++;
        }
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        for(int i = 0; i < n; i++){
            result.add(new ArrayList<>());
        }
        for(int i = 0; i < n; i++){
            result.get(leaderBuf[i]).add(i);
        }
        return result;
    }

}


Measured memory_bytes: 59832
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
const long long mod = 1e9+7;
const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};
const int ddx[4] = {1,1,-1, -1};
const int ddy[4] = {1,-1,-1,1};
//////////////////////////////////

int main(){
  int n; cin >> n;
  long long sum = 0;
  for(int i=0; i<=n; i++) {
    if (i%5==0 || i%3 == 0) continue;
    sum += i; 
  }
  cout << sum << endl;

  return 0;
}

// EOF


Measured memory_bytes: 3616
import java.lang.Math
import kotlin.comparisons.*

val MOD: Int = 1000000000 + 7
val MODL: Long = MOD.toLong()

fun main(args: Array<String>)
{
    val n = read().toInt()
    val d = read().split().toInt()
    val m = read().toInt()
    val t = read().split().toInt()

    val dm = mutableMapOf<Int, Int>()
    for (i in 0 until n) {
        if (d[i] in dm)
            dm.put(d[i], dm[d[i]]!! + 1)
        else dm.put(d[i], 1)
    }
    val tm = mutableMapOf<Int, Int>()
    for (i in 0 until m) {
        if (t[i] in tm) tm.put(t[i], tm[t[i]]!! + 1)
        else tm.put(t[i], 1)
    }

    var ans = true
    for (diff in tm.keys) {
        if (dm.containsKey(diff)) {
            if (dm[diff]!! >= tm[diff]!!) continue
            else {
                ans = false
                break
            }
        } else {
            ans = false
            break
        }
    }

    println(if (ans) "YES" else "NO")
}

fun read(): String = readLine()!!
fun CharSequence.split(): List<String> = this.split(" ")
fun Iterable<String>.toInt(): List<Int> = this.map{it.toInt()}
fun Iterable<String>.toLong(): List<Long> = this.map{it.toLong()}


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

int main() {
  char s[100], p[100];
  cin >> s >> p;

  char s2[200];
  strcat(s2, s);
  strcat(s2, s);

  if (strstr(s2, p) == NULL) {
    cout << "No" << endl;
  } else {
    cout << "Yes" << endl;
  }

  return 0;
}



Measured memory_bytes: 3088
package main

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

func main() {
	a := readi64()
	b := readi64()
	c := readi64()
	d := readi64()

	divC := (b / c) - ((a - 1) / c)
	divD := (b / d) - ((a - 1) / d)
	cd := lcm64(c, d)
	divCD := (b / cd) - ((a - 1) / cd)

	ans := (b - (a - 1)) - (divC + divD - divCD)

	fmt.Println(ans)
}

func lcm64(a, b int64) int64 {
	return (a * b) / gcd64(a, b)
}

func gcd64(a, b int64) int64 {
	if b == 0 {
		return a
	}
	return gcd64(b, a%b)
}

/*-------------------utilities-------------------*/

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func chmin(x *int, y int) bool {
	if *x > y {
		*x = y
		return true
	}
	return false
}

func chmax(x *int, y int) bool {
	if *x < y {
		*x = y
		return true
	}
	return false
}

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

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

func comb(n, k int) int {
	if n < k {
		return 0
	}
	if n < 0 || k < 0 {
		return 0
	}
	return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD
}

func permutations(arr []int) [][]int {
	var helper func([]int, int)
	res := [][]int{}

	helper = func(arr []int, n int) {
		if n == 1 {
			tmp := make([]int, len(arr))
			copy(tmp, arr)
			res = append(res, tmp)
		} else {
			for i := 0; i < n; i++ {
				helper(arr, n-1)
				if n%2 == 1 {
					tmp := arr[i]
					arr[i] = arr[n-1]
					arr[n-1] = tmp
				} else {
					tmp := arr[0]
					arr[0] = arr[n-1]
					arr[n-1] = tmp
				}
			}
		}
	}
	helper(arr, len(arr))
	return res
}

func isPrime(n int) bool {
	if n == 1 {
		return false
	}
	for i := 2; i*i <= n; i++ {
		if n%i == 0 {
			return false
		}
	}
	return true
}

func divisor(n int) (res []int) {
	for i := 1; i*i <= n; i++ {
		if n%i == 0 {
			res = append(res, i)
			if i*i != n {
				res = append(res, n/i)
			}
		}
	}
	sort.Ints(res)
	return
}

/*-------------------init-------------------*/

const (
	INF = 1000000000000000000
	MOD = 1e9 + 7

	COMB_MAX = 510000
)

var (
	readString func() string
)

var (
	fac  = [COMB_MAX]int{}
	finv = [COMB_MAX]int{}
	inv  = [COMB_MAX]int{}
)

func init() {
	readString = newReadString(os.Stdin)
}

func combInit() {
	fac[0] = 1
	fac[1] = 1
	finv[0] = 1
	finv[1] = 1
	inv[1] = 1
	for i := 2; i < COMB_MAX; i++ {
		fac[i] = fac[i-1] * i % MOD
		inv[i] = MOD - inv[MOD%i]*(MOD/i)%MOD
		finv[i] = finv[i-1] * inv[i] % MOD
	}
}

/*-------------------inputs-------------------*/

func readi() int {
	return int(readi64())
}

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

func readf() float64 {
	f, err := strconv.ParseFloat(readString(), 64)
	if err != nil {
		panic(err.Error())
	}
	return f
}

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

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


Measured memory_bytes: 640
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace Atcoder
{
    public class Program
    {
        public static void Main() { var r = GetResult(); Debug.WriteLine(r); Console.Write(r); }

        private static object GetResult()
        {
            var input = ReadLongs();

            long sheepcnt = input[0];
            long wolfcnt = input[1];

            if (sheepcnt <= wolfcnt)
            {
                return "unsafe";
            }
            return "safe";
        }

        #region Console

        public static string ReadText() { return Console.ReadLine(); }
        public static List<string> ReadTexts() { return Console.ReadLine().Split(' ').ToList(); }
        public static long ReadLong() { return long.Parse(Console.ReadLine()); }
        public static List<long> ReadLongs() { return Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToList(); }

        #endregion
    }
}



Measured memory_bytes: 28156
#include<bits/stdc++.h>
using namespace std;
#define lli long long int



int main()
{
	lli n,mw,ans,i,j;
	cin>>n>>mw;
	lli w[n+1],v[n+1];
	w[0]=v[0]=0;
	lli dp[n+1][mw+1];
	for(i=0;i<=n;i++)
	for(j=0;j<=mw;j++)
	dp[i][j]=0;
	
	for(i=1;i<=n;i++)
	{
		cin>>w[i]>>v[i];
	}
	dp[n+1][mw+1];
	for(i=0;i<=n;i++)
	{
		for(j=0;j<=mw;j++)
		{
			if(i==0 || j==0)
			dp[i][j]=0;
			else if(w[i]<=j)
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
			else
			dp[i][j]=dp[i-1][j];
		}
	}
	cout<<dp[n][mw];
}


Measured memory_bytes: 79104
#include<bits/stdc++.h>
using namespace std;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int q,q1,q2,q3,q4;
	cin>>q>>q1>>q2>>q3>>q4;
	if(!q){
		cout<<1;
	}
	else if(!q1){
		cout<<2;
	}
	else if(!q2){
		cout<<3;
	}
	else if(!q3){
		cout<<4;
	}
	else{
		cout<<5;
	}
	return 0;
}


Measured memory_bytes: 3568
#include<iostream>
#include<map>

using namespace std;

int main(){
    long long n, a;
    map<long long, int> mp;
    cin >> n;
    bool yes = true;
    for(int i=0;i<n;i++){
        cin >> a;
        mp[a]++;
        if(mp[a]>=2)yes=false;
    }
    cout << (yes?"YES":"NO") << endl;
}

Measured memory_bytes: 12800
io = DATA.eof? ? STDIN : DATA
$s=io.gets.chomp
$t=io.gets.chomp
s_s=$s.size
t_s=$t.size
def check(a,b)
  ar=a.size.times.map{|i|a[i]==b[i]}
  ar.count(true)
end

max=0
(0..s_s-t_s).each do |i|
  max=[check($s[i,t_s],$t),max].max
end
puts t_s-max
__END__


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

typedef vector<int> vi;
typedef pair<int, int> pii;
#define endl "\n"
#define sd(val) scanf("%d", &val)
#define ss(val) scanf("%s", &val)
#define sl(val) scanf("%lld", &val)
#define debug(val) printf("check%d\n", val)
#define all(v) v.begin(), v.end()
#define PB push_back
#define MP make_pair
#define FF first
#define SS second
#define ll long long
#define MOD 1000000007
#define clr(val) memset(val, 0, sizeof(val))
#define what_is(x) cerr << #x << " is " << x << endl;
#define OJ                            \
    freopen("input.txt", "r", stdin); \
    freopen("output.txt", "w", stdout);
#define FIO                           \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);

int main()
{
    // OJ;
    string s;
    cin >> s;
    int n = s.length();
    if (s[0] == '?')
        s[0] = 'D';

    for (int i = 1; i < n; i++)
    {
        if (s[i] == '?')
        {
            if (s[i - 1] == 'P')
            {
                s[i] = 'D';
            }
            else if (s[i - 1] == 'D' || i == n - 1)
            {
                s[i] = 'D';
            }
            else
            {
                s[i] = 'P';
            }
        }
    }

    cout << s << endl;

    return 0;
}

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

x = input().split()

a = [int(i) for i in x]

b = [0]*n
for j in range(0,len(a)):
    k = a[j] - 1
    b[k] = b[k] + 1

for i in range(0,n):
  print(b[i])


Measured memory_bytes: 92208
#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 INF 2e9
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
int GCD(int a,int b){return b?GCD(b,a%b):a;}
int LCM(int a,int b){return (a*b)/GCD(a,b);}
int abs(int x){return x>0?x:-x;}
 
//const int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
//const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

int main()
{
	string s, t;
	cin >> s >> t;
	int ans = 0;
	for (int i = 0; i < 3; i++){
		if (s[i] == t[i]) ans++;
	}
	cout << ans << endl;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define ll long long
const ll mod=1e9+7;

ll bigMod(ll n,ll p){
	if(p==1) return n;

	if(p%2==0){
		ll ret=bigMod(n,p/2);
		return ((ret%mod)*(ret%mod))%mod;
	}
	else return n*bigMod(n,p-1)%mod; 
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("C:\\Users\\User\\Documents\\input.txt","r",stdin);
#endif
	ll T,i,j;
	ll n;
	cin>>n;
	if(n<2) printf("0\n");
	else if(n==2) printf("2\n");
	else{
		ll res=(bigMod(10,n)-2*bigMod(9,n)+bigMod(8,n)+mod+mod)%mod;
		printf("%lld\n",res);
	}
		
		
	return 0;
}

Measured memory_bytes: 3732
#include <bits/stdc++.h>
#define ll long long
#define all(a) (a).begin(),(a).end()

using namespace std;

int main(int argc, char const *argv[]) {
  string A,B,C;
  std::cin >> A >> B >> C;
  if(A[A.size()-1]==B[0] && B[B.size()-1]==C[0]){
    printf("YES\n");
  }else{
    printf("NO\n");
  }
  return 0;
}


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

int main() {
    char b[101];

    cin >> b;

    int d=0;
    int q=0;
    int a=0;
    for(int i=0;i<101;i++) {
        if(b[i] == '\0') {
            a=i;
            break;
        }
    }
    char c[100];

    for(int i=0;i<a;i++) {
        bool hata = false;

        for(int j=0;j < q;j++) {
            if(b[i] == c[j]) {
                hata = true;
                break;
            }
        }

        if(hata == false) {
            for(int j=0;j<(a-i);j++) {
                if(b[i] == b[i+j]) {
                    d++;
                }
            }
            if(d % 2 > 0) {
                cout << "No";
                return 0;
            } else {
                d = 0;
                c[q] = b[i];
                q++;
            }
        }

    }
    

    cout << "Yes";

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define int long long
using namespace std;
typedef pair<int,int> P;
constexpr int mod=1e9+7;
int N,K;
int a[100];
class mint {
 private:
  int _num,_mod;
  mint set(int num){ 
      _num = num ;
      if(_num>=0) _num%=_mod;
      else _num+=(1-(_num+1)/_mod)*_mod; 
      return *this;
  }
  int mpow(int a,int n){
      int ans=1;
      while(n){
          if(n&1) ans*=a;
          a*=a;
          n/=2;
      }
      return ans;
  }
  int imod(int n){return mpow(n , _mod-2);}
 public:
  mint(){ _num = 0;_mod=mod; }
  mint(int num){ _mod = mod; _num = (num+(1LL<<30)*mod) % mod; }
  mint(int num,int M){ _mod=M;_num=(num+(1LL<<30)*mod)%_mod; }
  mint(const mint &cp){_num=cp._num;_mod=cp._mod;}
  mint operator= (const int x){ return set(x); }
  mint operator+ (const int x){ return mint(_num + (x % _mod) , _mod); }
  mint operator- (const int x){ return mint(_num - (x % _mod), _mod); }
  mint operator* (const int x){ return mint(_num * (x % _mod) , _mod); }
  mint operator/ (int x){ return mint(_num * imod(x) , _mod);}
  mint operator+=(const int x){ return set(_num + (x % _mod)); }
  mint operator-=(const int x){ return set(_num - (x % _mod)); }
  mint operator*=(const int x){ return set(_num * (x % _mod)); }
  mint operator/=(int x){ return set(_num * imod(x));}
  mint operator+ (const mint &x){ return mint(_num + x._num , _mod); }
  mint operator- (const mint &x){ return mint(_num - x._num , _mod);}
  mint operator* (const mint &x){ return mint(_num * x._num , _mod); }
  mint operator/ (mint x){ return mint(_num * imod(x._num) , _mod);}
  mint operator+=(const mint &x){ return set(_num + x._num); }
  mint operator-=(const mint &x){ return set(_num - x._num); }
  mint operator*=(const mint &x){ return set(_num * x._num); }
  mint operator/=(mint x){ return set(_num * imod(x._num));}

  bool operator<(const mint &x){return _num<x._num;}

  friend mint operator+(int x,const mint &m){return mint(m._num + (x % m._mod) , m._mod);}
  friend mint operator-(int x,const mint &m){return mint(m._num - (x % m._mod) , m._mod);}
  friend mint operator*(int x,const mint &m){return mint(m._num * (x % m._mod) , m._mod);}
  friend mint operator/(int x,mint m){return mint(m.imod(m._num) * x , m._mod);}

  friend ostream& operator<<(ostream &os, mint &x){ os << x._num; return os; }
  friend istream& operator>>(istream &is, mint &x){int val; is>>val; x.set(val); return is;}
};
signed main(){
    cin>>N>>K;
    REP(i,N) cin>>a[i];
    vector<vector<mint>> dp(N+1,vector<mint>(2*K+2,mint(0)));
    dp[N][K]=1;
    for(int i=N-1;i>=0;--i) for(int j=K;j>=0;--j){
        dp[i][j]=dp[i+1][j]+dp[i][j+1]-dp[i+1][j+a[i]+1];
    }
    cout<<dp[0][0]<<endl;
}



Measured memory_bytes: 319232
N,C,K=map(int,input().split())
T=[int(input()) for i in range(N)]
T.sort()
res=0#乗客
time=0#発車K分前
ans=0

for i in range(len(T)):
    if res!=0 and time+K<T[i]:
        ans+=1
        res=1
        time=T[i]

    else:
        res+=1
        if res==1:
            time=T[i]
        if res==C:
            ans+=1
            res=0

if res>0:
    ans+=1

print(ans)


Measured memory_bytes: 80996
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(ll i=0;i<n;i++)
#define FOR(i,n1,n2) for(ll i=n1;i<n2;i++)
#define bFOR(i,n1,n2) for(ll i=n1;i>=n2;i--)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long int ll;
typedef pair<ll,ll> Pi;
typedef tuple<ll,ll,ll> Tu;
const int INF=(ll)(1LL<<30)-1;
const double INFd=100000000000.0;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a, b)*b;}
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
int mdx[8]={0,1,0,-1,1,1,-1,-1},mdy[8]={-1,0,1,0,1,-1,1,-1};


template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int n;
int t[100100];
int a[100100];
int dh[100100];
int uh[100100];

int main(){
	cin>>n;
	REP(i,n){
		cin>>t[i];
		if(i!=0){
			if(t[i-1]>t[i]){
				cout<<0<<endl;
				return 0;
			}
		}
	}
	REP(i,n){
		cin>>a[i];
		if(i!=0){
			if(a[i-1]<a[i]){
				cout<<0<<endl;
				return 0;
			}
		}
	}
	REP(i,n){
		dh[i]=-1;
		uh[i]=-1;
	}
	dh[0]=t[0];
	FOR(i,1,n){
		if(t[i-1]<t[i]){
			dh[i]=t[i];
		}else{
			uh[i]=t[i];
		}
	}
	if(dh[n-1]!=-1){
		if(dh[n-1]!=a[n-1]){
			cout<<0<<endl;
			return 0;
		}
	}
	dh[n-1]=a[n-1];
	for(int i=n-2;i>=0;i--){
		if(a[i]>a[i+1]){
			if(dh[i]==-1){
				dh[i]=a[i];
			}else{
				if(dh[i]!=a[i]){
					cout<<0<<endl;
					return 0;
				}
			}
		}else{
			if(uh[i]==-1){
				if(dh[i]>a[i]){
					cout<<0<<endl;
					return 0;
				}
			}else{
				uh[i]=min(uh[i],a[i]);
			}
		}
	}
	ll ans=1;
	REP(i,n){
		
		if(dh[i]==-1){
			ans*=uh[i];
			ans%=MOD;
		}
	}/*
	REP(i,n)cout<<dh[i]<<" ";
	cout<<endl;
	
	REP(i,n)cout<<uh[i]<<" ";
	cout<<endl;*/
	
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1792
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    cout << n * (n - 1) / 2 + m * (m - 1) / 2 << endl;
    return 0;
}

Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
int s[100], c[100];
int ans[100];
int main(){
    int n, m;
    scanf("%d%d", &n, &m);

    for(int i=1;i<=m;i++){
        scanf("%d%d", &s[i], &c[i]);
    }
    int res = 1e9;
    for(int i=0;i<=999;i++){
        int x = i;
        int l = 1;
        if(i == 0){
            l = 1;
            ans[l] = 0;
        } 
        else{
            while(x){
                ans[l] = x%10;
                x/=10;
                l++;
            }
            l--;
        }

        if(l == n){
            bool ok = 1;
            for(int i=1;i<=m;i++){
                if(ans[n-s[i]+1] == c[i]) continue;
                ok = 0;
            }
            if(ok) res = min(res, i);
        }
    }
    if(res == 1e9) res = -1;
    printf("%d\n", res);
}

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
int main() {
	double n, x[100], t, p, s[4] = { 0 };
	scanf("%lf", &n);
	for (int i = 0; i < n; i++)
		scanf("%lf", &x[i]);
	for (int i = 0; i < n; i++) {
		scanf("%lf", &t);
		p = std::abs(x[i] - t);
		if (s[3] < p) s[3] = p;
		for (int j = 0; j < 3; j++)
			s[j] += pow(p, j + 1);
	}
	for (int i = 0; i < 3; i++)
		printf("%f\n", pow(s[i], 1.0 / (i + 1)));
	printf("%f\n", s[3]);
}

Measured memory_bytes: 1136
fun main() {
    val n= readLine()!!.toInt()
    val a= readLine()!!.split(" ").map { it.toInt() }
    val b= readLine()!!.split(" ").map { it.toInt() }
    val c= readLine()!!.split(" ").map { it.toInt() }
    var ans=0
    var bef=-1
    for (i in 0 until n){
        val now =a[i]-1
        if (bef!=-1 && now-bef==1){
            ans+=c[bef]
        }
        ans+=b[now]
        bef=now
    }
    println(ans)
}

Measured memory_bytes: 36376
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>


using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype
template <class T> int __builtin_popcount(T n) { return n ? 1 + __builtin_popcount(n & (n - 1)) : 0; }
#endif

#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define clear(arr, val) memset(arr, val, sizeof(arr))

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

template <class T> void max_swap(T& a, const T& b) { a = max(a, b); }
template <class T> void min_swap(T& a, const T& b) { a = min(a, b); }

typedef long long ll;
typedef pair<int, int> pint;

const double EPS = 1e-8;
const double PI = acos(-1.0);
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };



int main()
{
	int T;
	cin >> T;
	while (T--)
	{
		int init, year, n;
		cin >> init >> year >> n;
		int res = 0;
		while (n--)
		{
			int c, w;
			double rate;
			cin >> c >> rate >> w;
			int m = init;
			if (c == 0)
			{
				int t = 0;
				for (int i = 0; i < year; ++i)
				{
					t += m * rate;
					m -= w;
				}
				m += t;
			}
			else
			{
				for (int i = 0; i < year; ++i)
					m += m * rate - w;
			}
			max_swap(res, (int)m);
		}
		cout << res << endl;
	}
}

Measured memory_bytes: 0
#include <iostream>
#include <queue>
#include <utility>
using namespace std;

typedef pair<int, int> P;
const int W = 20, H = 20;
char board[H][W];

int bfs(int x, int y, int w, int h){
	int dx[] = {0, -1, 1, 0}, dy[] = {-1, 0, 0, 1}, c = 0;
	queue<P> q;
	q.push(make_pair(x, y));
	board[y][x] = '#';
	while(!q.empty()){
		P p = q.front();
		q.pop();
		++c;
		for(int i = 0;i < 4;++i){
			int nx = p.first + dx[i], ny = p.second + dy[i];
			if(0 <= nx && nx < w && 0 <= ny && ny < h && board[ny][nx] == '.'){
				q.push(make_pair(nx, ny));
				board[ny][nx] = '#';
			}
		}
	}
	return c;
}

int main(){
	int w, h, x, y;
	while(cin >> w >> h, w){
		for(int i = 0;i < h;++i){
			for(int j = 0;j < w;++j){
				cin >> board[i][j];
				if(board[i][j] == '@'){
					x = j;
					y = i;
				}
			}
		}
		cout << bfs(x, y, w, h) << endl;
	}
	return 0;
}

Measured memory_bytes: 1216
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main() {
	// your code goes here
	ll a,b;
	cin>>a>>b;
	if(a<=9 && b<= 9)
	{
		cout<<a*b;
	}
	else
	{
		cout<<"-1";
	}
	return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import *
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def I(): return int(sys.stdin.readline())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a = input()
    b = input()
    if a[2] == b[0] and a[1] == b[1] and a[0] == b[2]:
        print("YES")
    else:
        print("NO")
    return

#B
def B():
    n = I()
    n = int(math.sqrt(n))
    print(n**2)
    return

#C
def C():
    n = I()
    a = LI()
    a.sort()
    b = LI()
    b.sort()
    c = LI()
    c.sort()
    ans = 0
    for i in b:
        x = bisect_left(a, i)
        x = x * (n - bisect_right(c, i))
        ans += x
    print(ans)
    return

# D
# 解説AC
# 俺は正数問題を解いていたと思ったらいつのまにかグラフ問題を解いていた
# 何を言ってるかわからねーと思うが自分もわからねぇ(ｒｙ)
# 変態
# 全部の数字は足す1もしくは×10で考えられて前者なら全体の和が1増えて後者なら
# 変わらないということに気づいたらいけるんだと思う（いけるとは言ってない）
def D():
    k = II()
    dp = [inf] * k
    q = deque()
    q.append(1)
    dp[1] = 1
    while q:
        i = q.pop()
        if dp[(i * 10) % k] > dp[i]:
            dp[(i * 10) % k] = dp[i]
            q.appendleft((i * 10) % k)
        if dp[(i + 1) % k] > dp[i] + 1:
            dp[(i + 1) % k] = dp[i] + 1
            q.append((i + 1) % k)
    print(dp[0])
    return


#Solve
if __name__ == '__main__':
    D()


Measured memory_bytes: 60108
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
vector<bool> seen;
vector<vector<ll>> G;
queue<ll> Q;
struct UnionFind{
  vector<ll> par,siz;
  
  UnionFind(ll N):par(N+1),siz(N+1,1){
    for(int i=0; i<=N; i++)
      par[i]=i;
  }
  
  void mkpar1(ll parent, ll n){//親は最上位
    for(auto next_n: G[n]){
      if(seen[next_n]) continue;
      seen[next_n]=true;
      par[next_n]=parent;
      mkpar1(parent, next_n);
    }
  }
  
  void mkpar2(){//親は1個うえ
    while(!Q.empty()){
      ll v=Q.front();
      Q.pop();
      ll Gsz=G[v].size();
      for(ll i=0; i<Gsz; i++){
        ll next_v=G[v][i];
        if(seen[next_v]) continue;
        seen[next_v]=true;
        par[next_v]=v;
        Q.push(next_v);
      }
    }
  }
  
  ll root(ll x){
    if(par[x]==x)
      return x;
    return par[x]=root(par[x]);
  }
  
  void unite(ll x, ll y){
    ll rx=root(x), ry=root(y);
    if(rx==ry)
      return;
    par[ry]=rx;
    siz[rx]+=siz[ry];    
  }
  
  bool issame(ll x, ll y){
    return root(x)==root(y);
  }
  
  ll size(ll x){
    return siz[root(x)];
  }
};
int main(){
  ll N,M; cin>>N>>M;
  seen.assign(N+1,false);
  G.assign(N+1, vector<ll>(0,0));
  for(ll i=0; i<M; i++){
    ll a,b; cin>>a>>b;
    G[a].emplace_back(b);
    G[b].emplace_back(a);
  }
  UnionFind tree(N);
  Q.push(1);
  seen[1]=true;
  tree.mkpar2();
  for(ll i=2; i<=N; i++){
    if(tree.par[i]==i){
      cout<<"No"<<endl;
      return 0;
    }
  }
  cout<<"Yes"<<endl;
  for(ll i=2; i<=N; i++) cout<<tree.par[i]<<endl;
}

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

int num[3000];

int main(){
	int N;
	cin >> N;
	int L[N];
	for(int i=0; i<N; i++){
		cin >> L[i];
		for(int j=0; j<=L[i]; j++){
			num[j]++;
		}
	}
	sort(L, L+N);
	ll ans = 0;
	for(int i=2; i<N; i++){
		for(int j=i-1; j>=0; j--){
			if(num[L[i]-L[j]+1] > (N-j)){
				ans += num[L[i]-L[j]+1] - (N-j);
			}
		}
	}
	
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <set> 
#include <bitset>
#include <cmath>
using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0;i<n;i++)

int main () {
    
    int a,b; cin >> a >> b;

    cout << (a-1)*(b-1) << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <cstddef>
#include <complex>
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <array>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <limits>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <valarray>
#include <utility>
#include <tuple>
#include <cmath>
#include <memory>
#include <random>
#include <fstream>
#include <locale>
#include <bitset>

using ll = long long;
using ull = unsigned long long;

//vector
template <class T>
using vec = std::vector<T>;

template <class T>
using vvec = vec<vec<T>>;

constexpr std::size_t operator""_sz(ull n) { return std::size_t(n); }

ll gcd(ll a, ll b)
{
    if (a > b)
        std::swap(a, b);

    while (true)
    {
        auto m = b % a;
        if (m == 0)
            return a;
        b = a;
        a = m;
    }
}

int main()
{
    using namespace std;

    int n, k;
    cin >> n >> k;

    vec<ll> v(n);
    for (auto& e : v)
        cin >> e;

    // 左からl個、右からr個取りたいときの価値の合計
    auto takeLR = [n, k, &v](int l, int r){
        ll value{};
        vec<int> minuses;
        for (int i = 0; i < l && i < n; ++i)
        {
            value += v[i];
            if (v[i] < 0)
                minuses.push_back(v[i]);
        }
        for (int i = n - 1; i >= n - r  && i >= l && i >= 0; --i)
        {
            value += v[i];
            if (v[i] < 0)
                minuses.push_back(v[i]);
        }

        sort(minuses.begin(), minuses.end());
        auto d = k - l - r;
        int i{};
        while(d > 0 && i < minuses.size())
        {
            value -= minuses[i];
            --d;
            ++i;
        }
        
        return value;
    };

    ll ans{};
    for (int a = 0; a <= k; ++a)
        for (int l = 0; l <= a; ++l)
        {
            ans = max(ans, takeLR(l, a - l));
        }
    
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s;
	cin>>s;
	vector<int> v;
	for(int i=0;i<s.size();i++)
		if(s[i]!='A'&&s[i]!='C'&&s[i]!='G'&&s[i]!='T')
			v.push_back(i);
	if(v.empty())
	{
		cout<<s.size()<<endl;
		return 0;
	}
	int ans=0;
	for(int i=1;i<v.size();i++)
		ans=max(ans,v[i]-v[i-1]-1);
	ans=max(ans,v[0]);
	ans=max(ans,(int)s.size()-v[v.size()-1]-1);
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define lli long long int
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define se second;
#define fi first;
#define endl '\n';
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define REP(i,n) for (int i = 1; i <= n; i++)
template<typename T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<typename T> void chmin(T& a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T& a, T b) { if (a < b) a = b; }
typedef long long ll;
typedef vector<vector<ll> > matrix;
const ll MOD = 1000000007;
const int K = 9;
const lli mod = 1e9 + 7;
const lli INF = 1e9 + 7;
const lli N=2*1e5;
lli visit[400001];
map<lli,vector<lli> >g;
map<string,lli>pi,m1,m2;
lli var1,var2,var3,var4,var5,var6;
vector<lli>v,v1,v2,v3,v4;
lli X[10][10];
lli a[N],b[N],c[N];
lli n,m,l,t,r,q,p,k,x,y;
lli ans=0,ans1=0,ans2=0,ans3=0;
lli dp[N][3],cp[N][5];
int main(){
  _
  cin>>n;
  for(lli i=1;i<=n;i++){
    cin>>a[i]>>b[i]>>c[i];
  }
  for(lli i=1;i<=n;i++){
    dp[i][0]=max(dp[i-1][1]+a[i],dp[i-1][2]+a[i]);
    dp[i][1]=max(dp[i-1][0]+b[i],dp[i-1][2]+b[i]);
    dp[i][2]=max(dp[i-1][1]+c[i],dp[i-1][0]+c[i]);
  }
  cout<<max(max(dp[n][0],dp[n][1]),dp[n][2]);
}


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

int main() {
	int a, b;
	string s;
	cin >> a >> b >> s;
	bool f = true;
	for (int i = 0; i < s.size(); i++) {
		if (i == a) {
			f &= s[i] == '-';
		} else {
			f &= '0' <= s[i] && s[i] <= '9';
		}
	}
	cout << (f ? "Yes" : "No") << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define maxn 505
#define fi first
#define se second
using namespace std;
int n,mod,f[maxn][maxn];
pair<int,int>a[maxn];
int solve(int k){
	int cnt1=0,cnt2=0;
	f[0][0]=1;
	for(int i=0;i<2*n;i++)
		if(a[i].se==0){//front rb in [N,2N-1] + front choose.
			for(int j=0;j<=cnt2;j++)
				f[i+1][j]=1ll*f[i][j]*(a[i].fi-(cnt1+j)+1)%mod;
			cnt1++;
		}
		else{
			//lb-1, front rb in [N,2N-1] + front choose.
			for(int j=0;j<=cnt2;j++)
				f[i+1][j+1]=1ll*f[i][j]*(a[i].fi-(cnt1+j)+1)%mod;
			//rb, all rb in [N,2N-1] + front not choose(lb_i<lb_j -> rb_i<rb_j) + k
			f[i+1][0]=0;
			for(int j=0;j<=cnt2;j++)
				f[i+1][j]=(f[i+1][j]+1ll*f[i][j]*(a[i].se-(n+cnt2-j+k)+1))%mod;
			cnt2++;
		}
	return f[2*n][k];
}
int main()
{
	scanf("%d%d",&n,&mod);
	for(int i=0;i<n;i++)
		a[i].fi=ceil(sqrt(n*n-i*i))-1,a[i].se=sqrt(4*n*n-i*i);
	for(int i=n;i<2*n;i++)
		a[i].fi=sqrt(4*n*n-i*i),a[i].se=0;
	a[0].se=2*n-1,sort(a,a+2*n);
	int ans=0;
	for(int i=n;i>=0;i--) ans=(solve(i)-ans+mod)%mod;
	printf("%d\n",ans);
}

Measured memory_bytes: 4716
#include <bits/stdc++.h>
#define rep(i,n) for (ll i = 0; i < n; ++i)
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())
#define FORV(i, v) for (auto i = v.begin(); i != v.end(); i++)
using namespace std;

typedef long long ll;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const ll INF = 1e9;
const long long INFL = 1LL<<60;

const int mod = 1000000007;

int main()
{
  const int N = 13;
  string s;
  cin >> s;

  // 後ろから解くアルゴリズム
  // 1?2?3  0 -> 3 -> ?3 -> 2?3 -> ...

  vector<vector<ll>> dp(s.size() + 1, vector<ll>(N, 0));

  reverse(s.begin(), s.end());

  // 1行目を初期化する
  if (s[0] == '?') {
    for (int i = 0; i < 10; i++) dp[0][i] = 1;
  } else {
    dp[0][s[0] - '0'] = 1;
  }

  ll mul = 10;
  for (int i = 1; i < s.size(); i++) {
    char c = s[i];
    if (c == '?') {
      for (int k = 0; k < 10; k++) {
        for (int j = 0; j < N; j++) {
          dp[i][(k * mul + j) % N] += dp[i-1][j];
          dp[i][(k * mul + j) % N] %= mod;
        }
      }
    } else {
      int k = (int)(c - '0');
      for (int j = 0; j < N; j++) {
        dp[i][(k * mul + j) % N] += dp[i-1][j];
        dp[i][(k * mul + j) % N] %= mod;
      }
    }
    mul *= 10;
    mul %= N;
  }

  // rep(i, s.size()) {
  //   rep(j, 13) {
  //     cerr << dp[i][j] << " ";
  //   }
  //   cerr << endl;
  // }

  cout << dp[s.size()-1][5] << endl;

  return 0;
}


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


int main(){

ll n ;
cin >> n;
ll a,b;
ll min =20000000000;
ll ans;
for (ll i =1 ; i*i<=n; ++ i){
if ( n%i ==0)
{
  b = n/i;
  a = n/b;
  ans = a+b;
  min = (min , ans);
}

}
cout << min - 2 << endl;
}

Measured memory_bytes: 256