akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#define vel vector<long long>
#define veb vector<bool>
#define vvel vector<vel>
#define int long long
#define pin pair<int,int>
#define ppin pair<int,pin>
#define mkp make_pair
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
void mmin(int &a, int b) { a = min(a, b); }
void mmax(int &a, int b) { a = max(a, b); }
signed main() {
	int pr = 1000;
	pr *= pr * pr; pr += 7;
	int x, y, z; int k;
	cin >> x >> y >> z >> k;
	vel a(x), b(y);
	vel mar(x*y), c(z);
	rep(i, x) { cin >> a[i]; }
	rep(i, y) { cin >> b[i]; }
	rep(i, z) { cin >> c[i]; }
	rep(i, x) { rep(j, y) { mar[i*y + j] = a[i] + b[j]; } }
	sort(mar.begin(), mar.end());
	sort(c.begin(), c.end());
	priority_queue<ppin> pq;
	rep(i, z) { pq.push(mkp(c[i] + mar[x*y - 1],mkp(i,x*y-1))); }
	rep(ind, k) {
		ppin tp = pq.top(); pq.pop();
		cout << tp.first << endl;
		pin smt = tp.second;
		int fi = smt.first;
		int se = smt.second;
		if (smt.second > 0) {
			pq.push(mkp(c[fi] + mar[se - 1], mkp(fi, se - 1)));
		}
	}
	return 0;
}

Measured memory_bytes: 8192
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

public class Main {

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

		int n=in.nextInt();
		BT tree=new BT();
		PrintWriter out=new PrintWriter(System.out);

		for(int i=0;i<n;i++) {
			String odr=in.next();

			if(odr.equals("insert")) {
				int key=Integer.parseInt(in.next());
				tree.insert(key);
			}

			else if(odr.equals("find")) {
				int key=Integer.parseInt(in.next());
				if(tree.isExist(key))out.println("yes");
				else out.println("no");
			}

			else if(odr.equals("print")) {
				Queue<Integer> Q=new ArrayDeque<>(tree.walk('I'));
				while(!Q.isEmpty())out.print(" "+Q.remove());
				out.println();
				Q=tree.walk('F');
				while(!Q.isEmpty())out.print(" "+Q.remove());
				out.println();

			}
		}
		out.flush();
	}

}

class BTNode{
	int key;
	BTNode Parent,Left,Right;

	BTNode(int k){
		key=k;
	}
}

class BT{
	BTNode root,dummy;
	int NIL=-2000000001;
	int size=0;

	Queue<Integer> Q;

	BT(){
		root=new BTNode(NIL);
		dummy=new BTNode(NIL);
		root.Parent=dummy;
		root.Left=dummy;
		root.Right=dummy;
	}

	//insert
	void insert(int k) {
		if(size==0) {
			root.key=k;
			size++;
			return;
		}

		BTNode node=new BTNode(k),s=root,p=root;
		node.Left=dummy;node.Right=dummy;

		while(s!=dummy) {
			p=s;
			if(k<s.key)s=s.Left;
			else s=s.Right;
		}

		node.Parent=p;
		size++;

		if(k<p.key)p.Left=node;
		else p.Right=node;
	}

	//print
	Queue<Integer> walk(char odr) {
		Q=new ArrayDeque<>();
		if(odr=='F')preWalk(root);
		else if(odr=='I')inWalk(root);
		return Q;
	}

	void preWalk(BTNode node) {
		Q.add(node.key);
		if(node.Left!=dummy)preWalk(node.Left);
		if(node.Right!=dummy)preWalk(node.Right);
	}

	void inWalk(BTNode node) {
		if(node.Left!=dummy)inWalk(node.Left);
		Q.add(node.key);
		if(node.Right!=dummy)inWalk(node.Right);
	}

	//isExist
	boolean isExist(int key) {
		if(find(key,root)!=dummy)return true;
		else return false;
	}

	BTNode find(int key,BTNode node) {
		if(node==dummy)return dummy;
		if(node.key==key)return node;

		BTNode n;
		if(key<node.key)n=find(key,node.Left);
		else n=find(key,node.Right);

		return n;
	}

	//delete
	void delLeaf(BTNode node) {
		if(node.Parent.Left==node)node.Parent.Left=dummy;
		else node.Parent.Right=dummy;
	}

	void delSingle(BTNode node) {
		BTNode c;
		if(node.Left==dummy)c=node.Right;
		else c=node.Left;

		c.Parent=node.Parent;
		if(node.Parent.Left==node) node.Parent.Left=c;
		else node.Parent.Right=c;
	}

	void delDouble(BTNode node) {
		BTNode left=node.Left;
		node.key=left.key;

		if(left.Left!=dummy && left.Right!=dummy)delDouble(left);
		else if(left.Left!=dummy || left.Right!=dummy)delSingle(left);
		else delLeaf(left);
	}
}



Measured memory_bytes: 204476
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#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 <iomanip>
#include <array>
#include <numeric>
#include <regex>
#include <bitset>
#include <deque>

using namespace std;
typedef long long ll;
typedef pair<int, int> p_ii;

const int INF = 1e9;
const double PI = acos(-1.0);
const ll MOD = 1e9 + 7;

int d;
ll dcnt[11];
set<string> p753;

void creat753(int p, string x) {
	if (p == d) {
		if (x == "")return;
		p753.insert(x);
		return;
	}

	creat753(p + 1, x);

	if (dcnt[p] == 1) {
		creat753(p + 1, x + '3');
	}
	else if (dcnt[p] == 2) {
		creat753(p + 1, x + '3');
		creat753(p + 1, x + '5');
	}
	else if (dcnt[p] == 3) {
		creat753(p + 1, x + '3');
		creat753(p + 1, x + '5');
		creat753(p + 1, x + '7');
	}
	return;
}

int main() {

	string N;
	cin >> N;

	d = N.size();

	ll res = 0;
	for (int i = 0; i < d; i++) {
		ll t;
		if (i == 0) {
			if (i == 0 && N[i] < '3')continue;
			else if (N[0] >= '3' && N[0] < '5') t = 1;
			else if (N[0] >= '5' && N[0] < '7') t = 2;
			else if (N[0] >= '7') t = 3;
		}
		else {
			t=3;
		}
		dcnt[i] = t;
	}

	creat753(0, "");

	for (auto x : p753) {
		vector<bool> c(3, false);
		int dx = x.size();
		for (int i = 0; i < dx; i++) {
			if (x[i] == '3')c[0] = true;
			if (x[i] == '5')c[1] = true;
			if (x[i] == '7')c[2] = true;
		}



		bool flg = true;
		for (int i = 0; i < 3; i++) {
			if (!c[i])flg = false;
		}

		if (stoi(N) < stoi(x))flg = false;

		if (flg)res++;
	}


	cout << res << endl;

	return 0;
}

Measured memory_bytes: 3328
x,y = map(int,input().split())
n = abs(abs(y)-abs(x))
m = int(x*y==0)*(n+int(x>0)+int(y<0)) + int(x*y<0)*(n+1) + int(x*y>0)*(n+2*int(y*(abs(y)-abs(x))<0))
print(m)


Measured memory_bytes: 2940
#include"bits/stdc++.h"
#include<boost/multi_array.hpp>
#include<boost/range/irange.hpp>
#include<boost/range/algorithm.hpp>
#include<boost/range/adaptors.hpp>

namespace adaptor = boost::adaptors;

void solve()
{
    int64_t N, M, K;
    std::cin >> N >> M >> K;
    std::vector<int64_t> A(N), B(M);
    for (auto& v : A) std::cin >> v;
    for (auto& v : B) std::cin >> v;

    std::vector<int64_t> a(N + 1), b(M + 1);
    a[0] = 0;
    b[0] = 0;
    for (int64_t i = 0; i < N; i++) a[i + 1] = a[i] + A[i];
    for (int64_t i = 0; i < M; i++) b[i + 1] = b[i] + B[i];

    // Aをi冊 Bをj冊読む
    int64_t ans = 0;
    int64_t j = M;
    for (int64_t i = 0; i < N + 1; i++)
    {
        if (a[i] > K) break;
        while (b[j] > K - a[i]) j--;
        ans = std::max(ans, i + j);
    }

    std::cout << ans << std::endl;

}

int main()
{
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    solve();
}


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

def make_divs(n):
    divs = []
    
    for i in range(1, int(n**0.5)+1):
        if n%i==0:
            divs.append(i)
            
            if i!=n//i:
                divs.append(n//i)
    
    return divs

N, M = map(int, input().split())
ds = make_divs(M)
ans = 0

for d in ds:
    if M//d>=N:
        ans = max(ans, d)

print(ans)

Measured memory_bytes: 38640
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < n; i++)
static const long long INF = 1000000;
using p = pair<int64_t,int64_t>;

int main(){
    int k,n;
    cin >> k >> n;
    vector<int> vec(n);
    rep(i,n){
        int a;
        cin >> a;
        vec[i] = a;
    }
    int x = 0;
    rep(i,n-1){
        x = max(x,vec[i+1] - vec[i]);

    }
    x = max(x,k-vec[n-1]+vec[0]);
    int ans = k-x;
    cout << ans << endl;
}

Measured memory_bytes: 4024
import java.io.*;
import java.util.Scanner;


public class Main {

	private static Scanner sc;
	private static Printer pr;

	private static void solve() {
		int n = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();
		
		int[] p = new int[n];
		for (int i = 0; i < n; i++) {
			p[i] = sc.nextInt();
		}

		int l1 = 0, l2 = 0, l3 = 0;
		for (int i = 0; i < n; i++) {
			if (p[i] <= a) {
				l1++;
			} else if (p[i] <= b) {
				l2++;
			} else {
				l3++;
			}
		}
		
		pr.println(Math.min(l1, Math.min(l2, l3)));
	}

	// ---------------------------------------------------
	public static void main(String[] args) {
		sc = new Scanner(System.in);
		pr = new Printer(System.out);
			
		solve();
			
		pr.close();
		sc.close();
	}

	static class Printer extends PrintWriter {
		Printer(OutputStream out) {
			super(out);
		}
	}
}


Measured memory_bytes: 23764
import java.util.Scanner;
import java.util.stream.Stream;

public class Main {

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

		int[] line = Stream.of(sc.nextLine().split(" ", 0)).mapToInt(Integer::parseInt).toArray();
		int[] A_line = new int[line[0]];
		int[] B_line = new int[line[1]];
		int[] M_line = new int[3];

		int Amin = 1000000000;
		int Bmin = 1000000000;
		int let =0;

		Main main = new Main();


		for (int i = 0; i < line[0]; i++) {
			A_line[i] = sc.nextInt();
			if (Amin > A_line[i]) {
				Amin = A_line[i];
			}
		}

		for (int i = 0; i < line[1]; i++) {
			B_line[i] = sc.nextInt();
			if (Bmin > B_line[i]) {
				Bmin = B_line[i];
			}
		}

		int min = Amin+Bmin;


		for (int i = 0; i < line[2]; i++) {
			M_line[0] = sc.nextInt();
			M_line[1] = sc.nextInt();
			M_line[2] = sc.nextInt();
			let = A_line[M_line[0] - 1] + B_line[M_line[1] - 1] - M_line[2];
			if (let < min) {
				min = let;
			}
		}
		sc.close();

		System.out.println(min);
	}
}

Measured memory_bytes: 60908
import sys
def input():
    return sys.stdin.readline()[:-1]

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

cnt = 0
pre = -10
for i in range(N):
    a = A[i] - 1
    cnt += B[a]
    if pre+1 == a:
        cnt += C[pre]
    pre = a
print(cnt)

Measured memory_bytes: 3064
#include <iostream>
#include <map>
#include <queue>
#include <vector>

using namespace std;

typedef pair<int, int> P;
typedef vector<P> V;
typedef queue<int> Q;

class Solver {
    public:
        int n, m;
        int a[800], b[800], c[800];
        int solve() {
            int past_days[400];
            int prevs[400];
            V nexts[400];
            Q q;
            for (int i = 0; i < n; ++i) {
                nexts[i] = V();
                past_days[i] = -1;
                prevs[i] = 0;
            }
            for (int i = 0; i < m; ++i) {
                nexts[a[i]].push_back(P(b[i], c[i]));
                ++prevs[b[i]];
            }
            q.push(0);
            past_days[0] = 0;
            while (!q.empty()) {
                int k = q.front();
                q.pop();
                for (unsigned i = 0; i < nexts[k].size(); ++i) {
                    int nk = nexts[k][i].first;
                    int d = nexts[k][i].second;
                    past_days[nk] = max(past_days[nk], past_days[k] + d);
                    --prevs[nk];
                    if (prevs[nk] == 0) {
                        q.push(nk);
                    }
                }
            }
            return past_days[n - 1];
        }
};

int main() {
    Solver s;
    cin >> s.n >> s.m;
    for (int i = 0; i < s.m; ++i) {
        cin >> s.a[i] >> s.b[i] >> s.c[i];
    }
    cout << s.solve() << endl;
    return 0;
}

Measured memory_bytes: 1228
package main

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

func main() {
	N := nextInt()
	M := nextInt()
	var a, b, c []int
	for l := 0; l < M; l++ {
		a = append(a, nextInt()-1)
		b = append(b, nextInt()-1)
		c = append(c, -nextInt())
	}

	dist := make([]int, N)
	for i := 1; i < N; i++ {
		dist[i] = math.MaxInt64
	}

	for l := 0; l < N-1; l++ {
		for i := 0; i < M; i++ {
			if dist[a[i]] == math.MaxInt64 {
				continue
			} else if dist[b[i]] > dist[a[i]]+c[i] {
				dist[b[i]] = dist[a[i]] + c[i]
			}
		}
	}

	ans := -dist[N-1]

	negative := make([]bool, N)
	for l := 0; l < N; l++ {
		for i := 0; i < M; i++ {
			if dist[a[i]] == math.MaxInt64 {
				continue
			} else if dist[b[i]] > dist[a[i]]+c[i] {
				dist[b[i]] = dist[a[i]] + c[i]
				negative[b[i]] = true
			} else if negative[a[i]] {
				negative[b[i]] = true
			}
		}
	}

	if negative[N-1] {
		fmt.Println("inf")
	} else {
		fmt.Println(ans)
	}
}

// Input. ----------

var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Buffer([]byte{}, math.MaxInt64)
	sc.Split(bufio.ScanWords)
}

func nextInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}

	return i
}

func nextString() string {
	sc.Scan()
	if err := sc.Err(); err != nil {
		panic(err)
	}

	return sc.Text()
}

// ---------- Input.

// Util. ----------

func min(x, y int) int {
	return int(math.Min(float64(x), float64(y)))
}

func max(x, y int) int {
	return int(math.Max(float64(x), float64(y)))
}

// ---------- Util.


Measured memory_bytes: 896
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;
const int INF=1e9;

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

int main(){
    int c[3][3];
    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            cin>>c[i][j];
        }
    }
    for(int i=0; i<3; i++){
        c[1][i]-=c[0][i];
        c[2][i]-=c[0][i];
    }
    if(c[1][0]==c[1][1]&&c[1][0]==c[1][2]&&c[2][0]==c[2][1]&&c[2][0]==c[2][2]){
        cout<<"Yes"<<endl;
    }else cout<<"No"<<endl;

}


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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()

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

  string s;
  cin>>s;
  int c=0;
  for(int i=0;i<s.size();i++){
    if(s[i]!=s[s.size()-1-i]){
      c++;
      s[i]=s[s.size()-1-i];
    }
  }
  cout<<c<<endl;
  return 0;
}


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

int main() {
    vector<vector<char>> vec(3,vector<char> (3));
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            cin >> vec.at(i).at(j);
        }
    }
    for(int i = 0; i < 3; i++) {
        cout << vec.at(i).at(i);
    }
}

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

int main() {
    int x;
    int y;
    for(int i = 0;; i++){
        cin >> x >> y;
        if (x == 0 && y == 0) break;
        if (x <= y) cout << x << " " << y << endl;
        if (x > y) cout << y << " " << x << endl;
    }
    return 0;
}


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

int main()
{
  int op[4];
  int in;
  cin >> in;
  op[0] = in / 1000; in %= 1000;
  op[1] = in / 100; in %= 100;
  op[2] = in / 10;
  op[3] = in % 10;
  
  for (int bit = 0; bit < (1 << 3); ++bit) {
    int res = op[0];
    for (int i = 0; i < 3; ++i)
      res += (bit & (1 << i)) ? op[i+1] : -op[i+1];
    
    if (res == 7) {
      cout << op[0];
      for (int i = 0; i < 3; ++i) {
        if (bit & (1 << i)) cout << "+";
        else cout << "-";
        cout << op[i+1];
      }
      cout << "=7";
      return 0;
    }
  }
}


Measured memory_bytes: 256
def segfunc(x,y):
  return x|y

class SegmentTree(object):
    def __init__(self, A, dot, unit):
        n = 1 << (len(A) - 1).bit_length()
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._tree = tree
        self._dot = dot
        self._unit = unit

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r): #これで[l,r)から取り出す。
        l += self._n
        r += self._n
        l_val = r_val = self._unit
        while l < r:
            if l & 1:
                l_val = self._dot(l_val, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = self._dot(self._tree[r], r_val)
            l >>= 1
            r >>= 1
        return self._dot(l_val, r_val)


N = int(input())
S = str(input());Q = int(input())
A = []
for i in range(N):
  temp = S[i]
  num = ord(temp) - 97
  A.append(pow(2,num))
Tree = SegmentTree(A, segfunc, 0)
for i in range(Q):
  query = list(map(str,input().split()))
  if query[0] == "1":
    loc = int(query[1])-1 #0index
    num = ord(query[2])-97
    Tree.update(loc,pow(2,num))
  else:
    left = int(query[1])-1
    right = int(query[2])-1
    ret = Tree.sum(left,right+1)
    ans = 0
    for j in range(26):
      if (ret>>j)&1 == 1:
        ans += 1
    print(ans)


Measured memory_bytes: 118832
#include <bits/stdc++.h>
using namespace std;
const int dx[]={1,0,0,-1,1,-1,-1,1};
const int dy[]={0,1,-1,0,1,1,-1,-1};
const int INF = 1<<30;
const double EPS = 1e-8;
#define PB push_back
#define mk make_pair
#define fr first
#define sc second
#define reps(i,j,k) for(int i = (j); i < (k); ++i)
#define rep(i,j) reps(i,0,j)
#define MOD 1000000007
#define lengthof(x) (sizeof(x) / sizeof(*(x)))
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> Pii;
typedef pair<int,vi > P;
typedef unsigned long long ll;
ll D[100001];
ll IC[100001];
Pii cost[100001];
vector < Pii > imos;
int main(){
    int N,M;
    scanf("%d%d",&N,&M);
    rep(i,M){
        scanf("%lld",&D[i]);
        D[i]--;
    }
    rep(i,N-1){
        ll a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        cost[i] = Pii(a,b);
        IC[i] = c;
    }
    rep(i,M-1){
        ll a = min(D[i],D[i+1]);
        ll b = max(D[i],D[i+1]);
        imos.PB(Pii(a,1));
        imos.PB(Pii(b,-1));
    }
    sort(imos.begin(),imos.end());
    ll prev = -1;
    ll sum = 0;
    ll ans = 0;
    rep(i,imos.size()){
        if(prev != imos[i].fr){
            if(prev == -1){
                prev = imos[i].fr;
            }
            else{
                ll index = prev;
                while(index < imos[i].fr){
                    ans += min(cost[index].fr*sum,cost[index].sc*sum+IC[index]);
                    index++;
                }
                prev = imos[i].fr;
            }
        }
        sum += imos[i].sc;
    }

    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 5436
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
typedef long long lint;
const int N=2e5+5;
int n,q,buk[N];

namespace utils{
	template <class T> inline void apn(T &x,const T y){x=x<y?x:y;}
	template <class T> inline void apx(T &x,const T y){x=x>y?x:y;}
	inline int nxi(){
		int x=0;
		char c;
		while(((c=getchar())>'9'||c<'0')&&c!='-');
		const bool f=c=='-'&&(c=getchar());
		while(x=x*10-48+c,(c=getchar())>='0'&&c<='9');
		return f?-x:x;
	}
}
using namespace utils;

int main(){
	n=nxi(),q=nxi();
	for(int i=1; i<=n; ++i){
		++buk[nxi()];
	}
	std::sort(buk+1,buk+n+1);
	int ans=0;
	for(int i=1; i<=n-q; ++i){
		ans+=buk[i];
	}
	printf("%d\n",ans);
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long INF = 1LL<<60;
const int MOD = 1000000007;

ll GCD(ll x,ll y){
    if(y == 0) return x;
    else return GCD(y,x%y);
}
ll LCM(ll a,ll b){
    return a / GCD(a,b) * b;
}


int main() {
    int n; cin >> n;
    vector<double> v;
    for(int i = 0;i < n;i++){
        double x; cin >> x; v.push_back(x);
    }
    sort(v.begin(),v.end());
    double ans = (v[0]+v[1])/2;
    for(int i = 2;i < n;i++){
        ans = (ans+v[i])/2;
    }
    cout << fixed << setprecision(10) << ans;
}


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

int main() {
    int x,y;
    while (true) {
        cin >> x >> y;
        if (!x && !y) break;
        if (x > y) cout << y << ' ' << x << endl;
        else cout << x << ' ' << y << endl;
    }
    return 0;
}

Measured memory_bytes: 3092
/*
数据不清空，爆零两行泪。
多测不读完，爆零两行泪。
边界不特判，爆零两行泪。
贪心不证明，爆零两行泪。
动规顺序错，爆零两行泪。
大于少等号，爆零两行泪。
变量不统一，爆零两行泪。
越界不判断，爆零两行泪。
调试不注释，爆零两行泪。
溢出不 l l，爆零两行泪。
*/
#include<bits/stdc++.h>
using namespace std;
const int N=1000;
int n;
int a[N+1][N],ord[N+1][N+1];
int f[N+1][N+1];
bool vis[N+1][N+1];
void dp(int x,int y){
//	cout<<x<<" "<<y<<"\n";
	if(!x||!y){f[x][y]=0;return;}
	if(~f[x][y])return;
	if(vis[x][y])puts("-1"),exit(0);
	vis[x][y]=true;
	dp(x,a[x][ord[x][y]-1]);dp(y,a[y][ord[y][x]-1]);
	f[x][y]=max(f[x][a[x][ord[x][y]-1]],f[y][a[y][ord[y][x]-1]])+1;
	vis[x][y]=false;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)for(int j=1;j<n;j++)cin>>a[i][j],ord[i][a[i][j]]=j;
	memset(f,-1,sizeof(f));
	int ans=0;
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i!=j)dp(i,j),ans=max(ans,f[i][j]);
//	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i!=j)printf("dp(%d,%d)=%d\n",i,j,f[i][j]);
	cout<<ans;
	return 0;
}

Measured memory_bytes: 13056
#include<stdio.h>

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

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

const int INF = 1001001001;
const int mod = 1000000007;

ll pow(ll base, ll order) {
	ll ans = 1;
	rep(i,order - 1) ans *= base;
	return ans;
}

int gcd(int a, int b) {
	if (a < b) {
		int c = a;
		a = b;
		b = c;
	}
	if (b == 0) return a;
	return gcd (b, a % b);
}

ll sum(ll x) { // sum of subsequent numbers from 0 to x
	return x*(x + 1)/2;
}

int main() {
	string s;
	cin >> s;

	if (s == "ABC") {
		cout << "ARC" << endl;
		return 0;
	}
	else if (s == "ARC") {
		cout << "ABC" << endl;
		return 0;
	}
}


Measured memory_bytes: 3628
// lcmとかはg++ -std=c++17 default.cppみたいなかんじで
//vector<vector<ll>> piyo(tate,vector<ll> (yoko));

#include <bits/stdc++.h>
#define mod 1000000007
#define INF 1000000019
#define ll long long
#define ln cout<<endl;
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define double long double
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
using namespace std;
int dp[120][60000];
vector<int> w(2000);
vector<int> v(2000);

int main() {
    cin.tie(0);
   	ios::sync_with_stdio(false);
    //double mini=INF;
    int maxi=0,f=0,sum=0;
    string str,str1,str2;
    int i;
    double h;
    int n,x,m;
    int a,b,d,c;
    //int e,weight;
    int target;
    //targetが目的値、nが個数
    cin>>target>>n;
    
    //サイズをいい感じにする
    v.resize(n+1);

    //i番目の宝石の価値と重さを入力
    rep(i,n){
        cin>>v[i];
    }

    sort(v.begin(),v.end(),greater<int>());

    //DPテーブルを0で初期化(負のvが入るときは-INFとかにしたほうがよい?)
    for(ll i=0;i<n+1;i++){
        for(ll j=0;j<target+1;j++){
            dp[i][j]=INF;
        }
    }
    dp[0][0]=0;

    //DPテーブルの1行目からの入力
    REP(i,0,n){
        rep(j,target+1){
            dp[i+1][j]=min(dp[i+1][j],dp[i][j]);
            if(j>=v[i]){
                dp[i+1][j]=min(dp[i+1][j],dp[i][j-v[i]]+1);
                dp[i+1][j]=min(dp[i+1][j],dp[i+1][j-v[i]]+1);
            }
            //cout<<dp[i+1][j]<<" ";
        }
        //cout<<endl;
    }

    //dpテーブルのこたえにあたる部分を出力
    //i軸はn-1番目でj軸がw番目なところに注意する!
    cout<<dp[n][target]<<endl;


    return 0;
}



Measured memory_bytes: 7344
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {

	public static void main(String[] args) {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = "";

		ArrayList<String> ds = new ArrayList<String>();

		try {
			while ((s = br.readLine()) != null) {
				if (s.equals("0 0"))
					break;
				ds.add(s);
			}
		} catch (IOException e) {
			e.printStackTrace();
		}

		for (int i = 0; i < ds.size(); i++) {
			int year1 = Integer.parseInt((ds.get(i).split(" ")[0]));
			int year2 = Integer.parseInt((ds.get(i).split(" ")[1]));
			int count = 0;
			for (int j = year1; j <= year2; j++) {
				if (isLeep(j)) {
					System.out.println(j);
					count++;
				}
			}
			if (count == 0)
				System.out.println("NA");
			if (i != ds.size() - 1)
				System.out.println();
		}
	}

	public static boolean isLeep(int year) {

		boolean r = false;

		if (year % 4 == 0)
			r = true;

		if (year % 100 == 0)
			r = false;

		if (year % 400 == 0)
			r = true;

		return r;
	}

}

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

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

ll INF = 100000000000;

int main(){
  ll n, m, x;
  cin >> n >> m >> x;
  vector<ll> c(n);
  vector<vector<ll>> a(n);
  rep(i,n){
    cin >> c[i];
    rep(j,m){
      ll A;
      cin >> A;
      a[i].push_back(A);
    }
  }


  ll ans = INF;
  for(ll i = 0; i < 1 << n; i++){
    vector<ll> skill(m,0);
    ll cost = 0;
    rep(j,n){
      if(i>>j&1){
        cost += c[j];
        rep(k,m){
          skill[k] += a[j][k];
          // cout << a[j][k] << endl;
        }
      }
    }
    // cout << "i " << i << endl;
    // rep(j,m)cout << skill[j] << " ";
    // cout << endl;
    bool ok = true;
    rep(j,m){
      // cout << skill[j] << endl;
      if(skill[j]<x){
        ok = false;
        break;
      }
    }
    if(ok){
      ans = min(ans, cost);
    }
  }
  if(ans==INF){
    cout << -1 << endl;
  }else{
    cout << ans << endl;  
  }

  return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	ll k,r;
	cin>>k>>r;
	if(k<10){
		cout << r-100*(k-10);
	}
	else{
		cout <<r;
	}
	// your code goes here
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,k,x,y,t,p,q;
    cin>>n>>k>>x>>y;

    if(n>k)
    {   p=(k)*x;
        q=(n-k)*y;
        t=p+q;
        cout<<t;
    }
    else
    {
        p=n*x;
        t=p;
        cout<<t;
    }


    return 0 ;
}


Measured memory_bytes: 256
N = int(input())
T, A = map(int, input().split())
H = [0] + list(map(int, input().split()))

ans = 0
best = int(1e9)

for i in range(1, N+1):
    now =  abs(A - (T - H[i] * 0.006))
    if now < best:
        ans = i
        best = now
print(ans)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
 
int W,H,N;
vector<pair<int,int>>a;
 
main(){
	cin>>W>>H>>N;
	for(int i=1;i<=N;++i){
		int x1,y1,x2,y2;
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		if(x1==0|x1==W|y1==0|y1==H && x2==0|x2==W|y2==0|y2==H){
			for(int j=0;j<2;++j){
				if(y1==0){
					a.push_back({x1,i});
				}else if(x1==W){
					a.push_back({W+y1,i});
				}else if(y1==H){
					a.push_back({W+H+W-x1,i});
				}else if(x1==0){
					a.push_back({W+H+W+H-y1,i});
				}
				x1=x2;
				y1=y2;
			}
		}
	}
	sort(a.begin(),a.end());
	int s[100001]={0},i=0;
	for(auto b:a){
		int j=b.second;
		if(s[j]){
			if(s[j]!=i--){
				cout<<"NO";
				return 0;
			}
		}else{
			s[j]=++i;
		}
	}
	cout<<"YES";
}

Measured memory_bytes: 2420
#define rep(i,n) for (int i = 0; i < n; i++)
#define _USE_MATH_DEFINES
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <math.h>
#include <complex>
#include <cassert>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> p;
typedef complex<double> com;
const int mod = 1e9 + 7;
const int MOD = 998244353;
const ll inf = 1e18;


int main() {
	int n, k;
	cin >> n >> k;
	vector<ll> a(n);
	rep(i, n) {
		cin >> a[i];
	}
	vector<ll> sum;
	rep(i, n) {
		ll s = 0;
		rep(j, n - i) {
			s += a[j+i];
			sum.push_back(s);
		}
	}
	ll ans = 0;
	rep(i, 50) {
		int l = 49 - i;
		int cnt = 0;
		ll sub = ans + (1LL << l);
		for(auto& j:sum) {
			if ((sub&j)==sub) cnt++;
		}
		if (cnt >= k) ans = sub;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 6004
#include <bits/stdc++.h>
using namespace std;
string s;
int k;
int main() {
    ios_base::sync_with_stdio(0);
    cin >> s;
    cin >> k;
    for (int i=0;i<s.size();i++) {
        if (s[i]=='a') continue;
        int v='z'-s[i]+1;
        if (v<=k) {
            s[i]='a';
            k-=v;
        }
    }
    k=k%26;
    s[s.size()-1]+=k;
    if (s[s.size()-1]>'z') s[s.size()-1]='a'+s[s.size()-1]-'z'-1;
    cout << s << "\n";
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <cstdint>
#include <cctype>
#include <numeric>
#include <bitset>
#include <functional>

using namespace std;

using ll =  long long;
using Pll = pair<ll, ll>;
using Pii = pair<int, int>;

constexpr int INF = 1 << 30;
constexpr ll LINF = 1LL << 60;
constexpr ll MOD = 1000000007;
constexpr long double EPS = 1e-10;
constexpr int dyx[4][2] = {
    { 0, 1}, {-1, 0}, {0,-1}, {1, 0}
};
constexpr int N_MAX = 200000;

ll fact[N_MAX+1], rfact[N_MAX+1];

ll perm(ll n, ll k) {
    if(n-k < 0LL) return 0LL;
    return (fact[n] * rfact[n-k]) % MOD;
}

ll comb(ll n, ll k) {
    if(n-k < 0LL) return 0LL;
    return (perm(n, k) * rfact[k]) % MOD;
}

ll modpow(ll a, ll p) {
    ll ret = 1LL;
    while(p) {
        if(p & 1) {
            ret = (ret * a) % MOD;
        }
        a = (a * a) % MOD;
        p >>= 1;
    }
    return ret;
}

void init_fact(ll n) {
    fact[0] = fact[1] = 1;
    rfact[0] = rfact[1] = 1;
    for(ll i=2;i<=n;++i) {
        fact[i] = (fact[i-1] * i) % MOD;
        rfact[i] = modpow(fact[i], MOD-2);
    }
}

int n;
vector<int> graph[N_MAX];
vector<int> cnt_children(N_MAX, 0);
vector<ll> bottom_to_up(N_MAX, 1LL);
vector<ll> ans(N_MAX, 1LL);

void count_children(int node, int par) {
    for(int child: graph[node]) {
        if(child == par) continue;
        count_children(child, node);
        cnt_children[node] += cnt_children[child] + 1;
    }
}

void dfs(int node, int par) {
    ll n_child = cnt_children[node];
    for(int child: graph[node]) {
        if(child == par) continue;
        dfs(child, node);
        bottom_to_up[node] *= (comb(n_child, cnt_children[child]+1) * bottom_to_up[child]) % MOD;
        bottom_to_up[node] %= MOD;
        n_child -= cnt_children[child]+1;
    }
}

void dfs2(int node, int par, ll n_patterns) {
    for(int child: graph[node]) {
        if(child == par) continue;
        ll new_bottom_to_up = (bottom_to_up[node] * modpow(comb(cnt_children[node], cnt_children[child]+1), MOD-2)) % MOD * modpow(bottom_to_up[child], MOD-2) % MOD;
        ll top_to_down = comb(n-cnt_children[child]-2, n-cnt_children[node]-1) * n_patterns % MOD * new_bottom_to_up % MOD;
        ans[child] = comb(n-1, cnt_children[child]) * top_to_down % MOD * bottom_to_up[child] % MOD;
        dfs2(child, node, top_to_down);
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int a, b;
    cin >> n;
    init_fact(n);
    for(int i=0;i<n-1;++i) {
        cin >> a >> b;
        --a; --b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    count_children(0, -1);

    dfs(0, -1);
    ans[0] = bottom_to_up[0];
    dfs2(0, -1, 1);

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


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

int main () {
  double d, t, s;
  cin >> d >> t >> s;
  if (t >= (d / s)) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 3716
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  bool k = false;
  for(int i = 1;i < 10;i ++){
    for(int j = 1;j < 10;j ++){
      if(N == i*j){
        k = true;
      }
    }
  }
  if(k){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int Inf = 1000000001;
constexpr ll INF= 1e18;
constexpr ll MOD = 998244353;
const double PI = 3.1415926535897;
typedef pair<int,int> P;

int main() {
    int N;
    cin >> N;
    vector<int> two;
    vector<int> three;
    vector<int> six;
    for(int i = 1;i <= 30000;i++) {
        if(i % 6 == 0) {
            six.push_back(i);
        }
        else if(i % 2 == 0) {
            two.push_back(i);
        }
        else if(i % 3 == 0) {
            three.push_back(i);
        }
    }
    if(N == 3) {
        cout << "2 5 63" << endl;
    }
    else if(N == 4) {
        cout << "2 5 20 63" << endl;
    }
    else if(N == 6) {
        cout << "2 3 25 30 60 90" << endl;
    }
    else {
        int A = 0;
        int B = 0;
        int C = 0;
        for(int i = 1;i <= 10000;i++) {
            bool cnt = true;
            for(int j = 1;j <= 5000;j++) {
                if(i % 2 == 0 && j % 2 == 0) {
                    if(N >= i + j && N - (i + j) <= 5000) {
                        A = i;
                        B = j;
                        C = N - A - B;
                        cnt = false;
                        break;
                    }
                }
            }
            if(cnt == false) {
                break;
            }
        }
        for(int i = 0;i < A;i++) {
            cout << two.at(i) << " ";
        }
        for(int i = 0;i < B;i++) {
            cout << three.at(i) << " ";
        }
        for(int i = 0;i < C;i++) {
            cout << six.at(i) << " ";
        }
        cout << endl;
    }
}

Measured memory_bytes: 512
def is_war_by_list(x_list, y_list) :
	max_x = max(x_list)
	min_y = min(y_list)
	
	if (max_x < min_y) :
		return False
	else :
		return True

def is_war_by_number(x,y,z) :
	if (x < z and z <= y) :
		return False
	else :
		return True
	

# あ
read_line = [int(i) for i in input().split()]
N = read_line[0]
M = read_line[1]
X = read_line[2]
Y = read_line[3]

x_list = [int(i) for i in input().split()]
y_list = [int(i) for i in input().split()]

if (is_war_by_list(x_list,y_list) or is_war_by_number(X,Y, min(y_list))) :
	print("War")
else :
	print("No War")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
#define print(n) cout << n << endl
#define in(v) int v; cin >> v
#define vint vector<int>
#define pb push_back
typedef long long int ll;

int main(){
  string s;
  cin>>s;
  if(s=="ABC"){
    print("ARC");
  }else{
    print("ABC");
  }
  return 0;
}

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

#define M 1000000007
#define MM 998244353 
#define ll long long 
#define pb push_back
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define memf(a) memset(a,false,sizeof(a))
#define all(v) v.begin(),v.end()
#define sz(a) (ll)a.size()
#define F first
#define S second
#define PI 3.1415926536
#define INF 2000000000000000000
#define endl "\n"
#define _time_ 1.0 * clock() / CLOCKS_PER_SEC
#define popcount(x) __builtin_popcountll(x)
//RNG based on mersenne_twister 
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll power(ll b,ll e,ll m)
{
	if(e==0) return 1;
	if(e&1) return b*power(b*b%m,e/2,m)%m;
	return power(b*b%m,e/2,m);
}
ll power( ll b, ll e)
{
	if(e==0) return 1;
	if(e&1) return b*power(b*b,e/2);
	return power(b*b,e/2);
}
template<typename T, typename U> static inline void amin(T &x, U y){ if(y<x) x=y; }
template<typename T, typename U> static inline void amax(T &x, U y){ if(x<y) x=y; }


int _runtimeTerror_()
{
	ll s,w;
	cin>>s>>w;
	if(w>=s)
		cout<<"unsafe";
	else cout<<"safe";
	return 0;
}

int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	#ifdef runSieve
		sieve();
	#endif
	#ifdef NCR
		initialize();
	#endif
	int TESTS=1;
	//cin>>TESTS;
	while(TESTS--)
		_runtimeTerror_();
	cerr<<"\n"<<_time_;
	return 0;
}


Measured memory_bytes: 3804
K, N = map(int, input().split())
A = list(map(int, input().split()))
lst = []
for i in range(1, N-1):
    diff_1 = abs(A[i + 1] - A[i])
    lst.append(diff_1)
    diff_2 = abs(A[i] - A[i - 1])
    lst.append(diff_2)

lst.append
lst.append(K + A[0] - A[N-1])
print(K - max(lst))

Measured memory_bytes: 26420
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <queue>
#include <functional>
#include <vector>
#include <stack>
#include <set>
#include <bitset>
using namespace std;
typedef  long long ll;
const int maxn=1e6+50;
const int inf=0x3f3f3f3f;
const int MOD=1e9+7;
const int HASH=131;

ll a[maxn];
ll b[maxn];

int main()
{
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        int tmp;
        cin>>tmp;
        a[i]=a[i-1]+tmp;
    }
    for(int i=1;i<=m;i++)
    {
        int tmp;
        cin>>tmp;
        b[i]=b[i-1]+tmp;
    }
    int ans=0;
    for(int i=0;i<=n&&a[i]<=k;i++)
    {
        int l=0,r=m;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(a[i]+b[mid]>k) r=mid-1;
            else
            {
                l=mid+1;
                ans=max(ans,i+mid);
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 6856
#include <iostream>

int main() {
  long a, b, c;

  std::cin >> a;
  std::cin >> b;
  std::cin >> c;

  if (a + b >= c)
    std::cout << "Yes" << std::endl;
  else
    std::cout << "No" << std::endl;

  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3121000;
long long fact[C_SIZE];
long long finv[C_SIZE];
long long inv[C_SIZE];
long long Comb(int a,int b){
 	if(a<b||b<0)return 0;
 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
}
void init_C(int n){
	fact[0]=finv[0]=inv[1]=1;
	for(int i=2;i<n;i++){
		inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	}
	for(int i=1;i<n;i++){
		fact[i]=fact[i-1]*i%mod;
		finv[i]=finv[i-1]*inv[i]%mod;
	}
}
long long pw(long long a,long long b){
	long long ret=1;
	while(b){
		if(b%2)ret=ret*a%mod;
		a=a*a%mod;
		b/=2;
	}
	return ret;
}
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
double ABS(double a){return max(a,-a);}
// ここから編集しろ
int b[110000];
int lis[110000];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%d",b+i);
		b[i]++;
	}

	lis[0]=-mod;
	int ret=0;
	for(int i=0;i<a;i++){
		int at=upper_bound(lis,lis+i+1,-b[i])-lis;
		lis[at]=min(lis[at],-b[i]);
		ret=max(ret,at);
	}
	printf("%d\n",ret);
}

Measured memory_bytes: 896
N,Q = map(int,input().split())
S = input()
t = [0]*(N+1)

for i in range(N):
    t[i+1] = t[i] + (1 if S[i:i+2]=="AC" else 0)

for i in range(Q):
    r,l = map(int,input().split())
    print(t[l-1]-t[r-1])

Measured memory_bytes: 7748
#include <bits/stdc++.h>
#include <stdint.h>
#include <algorithm>
#include <vector>


using namespace std;

int main() {
	int a,b;
	cin >> a >> b;
	
	if(a<10 && b<10){
		cout << a*b << endl;
	} else {
		cout << -1 << endl;
	}
	


	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
//#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cassert>
using namespace std;
typedef long long ll;
const int Nmax = 1e5;
ll N;
ll A[Nmax];

template <class T>
class Bit{
	vector<T> v;
	public:
	Bit(int n) {
		v = vector<T>(n);
	}
	// i must be 0 <= i < n
	T sum(int i){
		T s=0;
		while(i>0){
			s += v[i];
			i -= i & -i;
		}
		return s;
	}
	// i must be 1 <= i < n
	void add(int i, T x){
		while(i < v.size()){
			v[i] += x;
			i += i & -i;
		}
	}
};

int main(){
	cin >> N;
	for(int i=0; i<N; i++) cin >> A[i];

	ll lb=0, ub=1e9+5;
	vector<ll> cum(N+1);
	while(ub-lb>1){
		ll x = (lb+ub)/2;
		for(int i=0; i<N; i++){
			cum[i+1] = cum[i]+(A[i]>=x?1:-1);
		}
		ll c = 0;
		Bit<int> bit(2*N+2);
		for(int i=0; i<=N; i++){
			c += bit.sum(1+N+cum[i]);
			bit.add(1+N+cum[i], 1);
			if(1+N+cum[i]<=0 || 1+N+cum[i]>=2*N+2)
				cout << x << " " << i << " " << 1+N+cum[i] << endl;
		}
		//cout << x << " " << c << endl;
		if(c >= (1+N*(N+1)/2)/2){
			lb = x;
		} else {
			ub = x;
		}
	}

	cout << lb << endl;

	return 0;
}


Measured memory_bytes: 2572
import Math._
import scala.util.control.Breaks
object Main extends App {
  val bk = Breaks

  var x = 0.0
  var y = 0.0
  var a = toRadians(90.0)

  bk.breakable {
    while (true) {
      val Seq(td, ta) = readLine().split(',').map(_.toInt).toList
      if (td == 0 && ta == 0) bk.break()

      x += td * cos(a)
      y += td * sin(a)
      a -= toRadians(ta)
    }
  }

  println(x.toString.split('.')(0))
  println(y.toString.split('.')(0))
}


Measured memory_bytes: 44036
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>v, w;


int main() {

	int N, W;
	cin >> N >> W;

	
	v.resize(N); w.resize(N);
	//入力
	for (int i = 0; i < N; i++) {
		cin >> v[i] >> w[i];

	}

	//それぞれの重さの時の最大の価値
	int MaxValue[10001] = { 0 };

	//与えられたものを一個ずつ入れる場合の最大の価値を算出
	//重さiのものを入れる時の価値を計算していく。
	//重さ9のものを入れた場合の最大の価値を計算する。
	//Wから計算していくのは20-9==11としたときに11の重さの時の最大の価値を重さ9を使って計算してしまっていて、同じ重りを使うことになってしまうため。
	for (int i = 0; i < N; i++) {
		for (int j = 1; j<=W; j++) {
			if (j - w[i] >= 0) {
				MaxValue[j] = max(MaxValue[j], MaxValue[j - w[i]] + v[i]);
			}
		}

	}

	cout << MaxValue[W] << "\n";

	return 0;
}



Measured memory_bytes: 3160
#include<bits/stdc++.h>
#define M 100007
using namespace std;
int n,m,s,t;
vector<int>q[M];
struct no{
	int a,step;
};
bool flag[M][3];
int spfa(int s,int t){
	queue<no>Q;
	Q.push((no)<%s,0%>);
	while(!Q.empty()){
		no z=Q.front();
		Q.pop();
		if(z.a==t&&z.step%3==0)return z.step/3;
		for(int i=0;i<(int)q[z.a].size();i++){
			if(flag[q[z.a][i]][(z.step+1)%3])continue;
			flag[q[z.a][i]][(z.step+1)%3]=1;
			Q.push((no)<%q[z.a][i],z.step+1%>);
		}
	}
	return -1;
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1,u,v;i<=m;i++){
		scanf("%d%d",&u,&v);
		q[u].push_back(v);
	}
	scanf("%d%d",&s,&t);
	printf("%d\n",spfa(s,t));
	return 0;
}

Measured memory_bytes: 6016
//use itertools::Itertools;
use std::cmp;
use std::collections::BTreeMap;
use std::collections::BTreeSet;
use std::collections::BinaryHeap;
use std::collections::HashMap;
use std::collections::HashSet;
use std::collections::VecDeque;
use std::io::Read;
use std::usize::MAX;

macro_rules! input {(source = $s:expr, $($r:tt)*) => {let mut iter = $s.split_whitespace();let mut next = || { iter.next().unwrap() };input_inner!{next, $($r)*}};($($r:tt)*) => {let stdin = std::io::stdin();let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));let mut next = move || -> String{bytes.by_ref().map(|r|r.unwrap() as char).skip_while(|c|c.is_whitespace()).take_while(|c|!c.is_whitespace()).collect()};input_inner!{next, $($r)*}};}
macro_rules! input_inner {($next:expr) => {};($next:expr, ) => {};($next:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($next, $t);input_inner!{$next $($r)*}};}
macro_rules! read_value {($next:expr, ( $($t:tt),* )) => {( $(read_value!($next, $t)),* )};($next:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()};($next:expr, chars) => {read_value!($next, String).chars().collect::<Vec<char>>()};($next:expr, usize1) => {read_value!($next, usize) - 1};($next:expr, [ $t:tt ]) => {{let len = read_value!($next, usize);(0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()}};($next:expr, $t:ty) => {$next().parse::<$t>().expect("Parse error")};}

fn solve() {
    input! {
        n: usize
    }

    let mut ans = 0;

    let mut i = 1;
    while i <= n {
        let num = n / i; // 個数
        let sum = i * num * (num + 1) / 2;
        ans += sum;
        i += 1;
    }

    /*
    while i <= n {
        ans += i;
        i += 1;
    }
    */

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

fn main() {
    let thd = std::thread::Builder::new().stack_size(104_857_600);
    thd.spawn(|| solve()).unwrap().join().unwrap();

    /*
    // 入力を一括で読み込む場合
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let mut input = buf.split_whitespace();

    // inputに対しnext()で読み込んでいく
    let q: usize = input.next().unwrap().parse().unwrap();
    */
}

const LARGE_PRIME: u64 = 1_000_000_007;

// @〜でsnippet
// 約数の列挙
fn enumerate_divisor(n: usize) -> Vec<usize> {
    let mut i = 1;

    let mut divisors = vec![];

    while i * i <= n {
        if n % i == 0 {
            divisors.push(i);
            divisors.push(n / i);
        }
        i += 1;
    }

    divisors.sort();

    divisors
}


Measured memory_bytes: 2252
#include <stdio.h>

int main(){
  int d, n;
  scanf("%d%d", &d, &n);
  if(d == 0) printf("%d\n", n + (n==100));
  else if(d == 1) printf("%d\n", (n+(n==100))*100);
  else if(d == 2) printf("%d\n", (n+(n==100))*10000);
  return 0;
}


Measured memory_bytes: 128