akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#include <iostream>
#include <string>
#include <map>
#include <set>
#include <functional>
#include <iostream>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n;
int r[101];
int s[101][3];
int gp[101][3];
int sum[101];

bool C(int v,int x){
	s[0][v]+=x;
	memset(sum,0,sizeof(sum));
	for(int i=0;i<3;i++){
		for(int j=0;j<n;j++){
			int cnt=0;
			for(int k=0;k<n;k++){
				if(j==k)continue;
				if(s[j][i]<s[k][i])cnt++;
			}
			sum[j]+=r[cnt];
		}
	}
	s[0][v]-=x;
	int cnt=0;
	for(int i=1;i<n;i++){
		if(sum[0]<sum[i])cnt++;
	}
	return (cnt<8);
}

int main(void){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&r[i]);
	}
	for(int i=0;i<n;i++){
		scanf("%d%d%d",&s[i][0],&s[i][1],&s[i][2]);
	}
	int res=101;
	for(int i=0;i<3;i++){
		int l=-1,r2=101;
		while(r2-l>1){
			int mid=(l+r2)/2;
			if(C(i,mid))r2=mid;
			else l=mid;
		}
		res=min(res,r2);
	}
	if(res==101)printf("Saiko\n");
	else printf("%d\n",res);
	return 0;
}

Measured memory_bytes: 3164
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 1000000000; //10^9

int main(){
    int N; cin >> N;
    vector<int> v(N);
    for(int i = 0; i < N; i++){
        cin >> v.at(i);
    }
    sort(v.begin(), v.end());
    int ans = v[v.size() / 2] - v[v.size() / 2 - 1];
    cout << ans << endl;
}


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

class Edge {
public:
	Edge(int source, int target, int cost) :
		firstVec(source), secondVec(target), weight(cost) {};

	int GetFirstVec() { return firstVec; }
	int GetSecondVec() { return secondVec; }
	int GetWeight() const{ return weight; }

	bool operator < (const Edge &e) const{
		return weight < e.GetWeight();
	}

private:
	int firstVec, secondVec, weight;
};

enum Query {
	Unit,
	Same,
};

class DisjointSet {
public:
	DisjointSet(int size) {
		rank.resize(size, 0);
		parent.resize(size, 0);
		for (int i = 0; i < size; i++) {
			MakeSet(i);
		}
	}

	bool Same(int x, int y) {
		return FindSet(x) == FindSet(y);
	}

	void Unit(int x, int y) {
		Link(FindSet(x), FindSet(y));
	}

private:
	void Link(int x, int y) {
		if (rank[x] > rank[y])
			parent[y] = x;
		else {
			parent[x] = y;
			if (rank[x] == rank[y])
				rank[y]++;
		}
	}

	//???????????°????????????
	//?????????????????????????????????????????????FindSet??????????????????????????????
	//(???????????????return????????¨???????????????????????????????????§???????????°??????????????????
	//????????\???????????????????????§???????????°??????????????????)
	void MakeSet(int x) {
		parent[x] = x;
		rank[x] = 0;
	}

	//?????????????????????
	//????????§???????????????????????°????????????????´°???p320???
	int FindSet(int x) {
		if (x != parent[x])
			parent[x] = FindSet(parent[x]);
		return parent[x];
	}

	vector<int> rank;
	vector<int> parent;
};

int Kruskal(vector<Edge> &edges, int vecNum) {

	sort(edges.begin(), edges.end());
	DisjointSet disSet = DisjointSet(vecNum+1);

	int firstVec, secondVec;
	int totalWeight = 0;
	for (int i = 0; i < edges.size(); i++) {

		Edge e = edges[i];
		if (!disSet.Same(e.GetFirstVec(), e.GetSecondVec())) {
			disSet.Unit(e.GetFirstVec(), e.GetSecondVec());
			totalWeight += e.GetWeight();
		}
	}

	return totalWeight;
}

int main() {

	int vecNum;
	int edgeNum;
	vector<Edge> edges;

	cin >> vecNum >> edgeNum;
	for (int i = 0; i < edgeNum; i++) {
		int firstVec, secondVec, weight;
		cin >> firstVec >> secondVec >> weight;
		edges.push_back(Edge(firstVec, secondVec, weight));
	}

	int weightNum = Kruskal(edges, vecNum);
	cout << weightNum << endl;

	return 0;
}

Measured memory_bytes: 4476
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <iomanip>
#include <set>
#include <map>

using namespace std;

int main(){
    int x;
    cin >> x;
    
    vector<char> s;
    if(x==0){
        cout << "0";
        return 0;
    }
    while(x!=0){
        if(x%2==0){
            s.push_back('0');
            x/=(-2);
        }else{
            s.push_back('1');
            x=(x-1)/(-2);
        }
    }
    for(auto i=s.end()-1;i>=s.begin();i--){
        cout << (*i);
    }
    
    
    
    return 0;
    
}
    
    
    
    
    
    
    

Measured memory_bytes: 256
import sys
import math
from collections import deque
import heapq
import itertools
import bisect
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = IL()

for i in range(N):
  a[i] -= i
#print(a)

b = a[:]
b.sort()

#print(b)
ans = 0
for i in range(N):
  num = -((i+1) - 1)*2 - a[i]
  #print(i+1, num)
  #print(bisect.bisect_right(b, num))
  #print(bisect.bisect_left(b, num))
  #print("---")
  ans += bisect.bisect_right(b, num) - bisect.bisect_left(b, num)
print(ans)

Measured memory_bytes: 92092
(defun input (n)
  (let ((a (make-array n)))
    (loop for i below n do (setf (aref a i) (read)))
    a)) 

(defun solve (n A)
  (let ((ans 0)
        (maxi (reduce #'max A)))
    (loop for i from 0 below n 
          for ai = (aref A i)
          for x = (abs (- (/ maxi 2) ai))
          when (< x (abs (- (/ maxi 2) ans)))
          do (setq ans ai))
    (cons maxi ans))) 

(let* ((n (read))
      (a (input n))
      (e (solve n a)))
  (format t "~A ~A~%" (car e) (cdr e)))

Measured memory_bytes: 67808
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[][][] cnt = new int[4][3][10];
        int n = sc.nextInt();
        for(int i=0; i<n; i++){
            int b = sc.nextInt() - 1, f = sc.nextInt() - 1;
            int r = sc.nextInt() - 1, v = sc.nextInt();
            cnt[b][f][r] += v;
        }

        for(int i=0; i<4; i++){
            for(int j=0; j<3; j++){
                for(int k=0; k<10; k++){
                    System.out.print(" "+cnt[i][j][k]);
                }
                System.out.println();
            }
            if(i<3) System.out.println("####################");
        }
    }
}


Measured memory_bytes: 29080
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define endl "\n"
#define se second
#define ll long long
#define inf 0x3f3f3f3f
#define fast    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N = 2e5+5;
const ll mod =   1e9+7;
int arr[N][2];int n;
int main()
{  fast
cin>>n;
for(int i=0;i<n;i++)
cin>>arr[i][0]>>arr[i][1];
int cnt=0;
for(int i=0;i<n;i++){
	if(arr[i][0]==arr[i][1])
	cnt++;
	else
	cnt=0;
	if(cnt>=3)
	{
		cout<<"Yes\n";return 0;
	}
}
cout<<"No\n";
}

Measured memory_bytes: 3644
import fractions

A,B,C,D = input().strip().split(" ")
A = int(A)
B = int(B)
C = int(C)
D = int(D)
X = C*D // fractions.gcd(C,D)

c = B//C - A//C + int(A%C == 0)
d = B//D - A//D + int(A%D == 0)
cd = B//X - A//X + int(A%X == 0)

delim = c + d - cd
result = B - A + 1 - delim 
print(result)

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

using namespace std;
using ll = long long;

const ll mod = (ll)1e9 + 7;

vector<bool> numbers;
vector<int> primes;
map<int, int> facts;

void collect_primes(const int n) {
    numbers.resize(n, true);
    for (int i = 2; i * i <= n; i++) {
        if (numbers[i]) {
            primes.push_back(i);
            for (int k = i; k * k <= n; k += i) {
                numbers[k] = false;
            }
        }
    }
}

void factorize(const int n) {
    int x = n;
    for (int i = 0; i < (int) primes.size(); i++) {
        int prime = primes[i];
        int c = 0;
        while (x % prime == 0) {
            c++;
            x /= prime;
        }
        facts[prime] = max(facts[prime], c);
    }
    if (x != 1) {
        facts[x] = max(facts[x], 1);
    }
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b % mod);
}

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

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    collect_primes(1e6 + 1);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        factorize(a[i]);
    }
    ll lcm = 1;
    for (auto e: facts) {
        for (int i = 0; i < e.second; i++) {
            lcm *= e.first;
            lcm %= mod;
        }
    }
    ll ans = 0;
    for (auto ai: a) {
        ans += lcm * rep_pow(ai, mod - 2) % mod;
        ans %= mod;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 896
package main

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

func main() {
	sc := NewBufScanner(os.Stdin)
	n := sc.Int()

	a := make(map[int]int, 1e5+1)
	var sum uint64
	for i:= 0; i < n; i++ {
		tmp := sc.Int()
		a[tmp]++
		sum += uint64(tmp)
	}

	// sort.Ints(a)
	q := sc.Int()

	for i:= 0; i < q; i++ {
		b, c := sc.Int(), sc.Int()
		sum -= uint64(a[b]*b - a[b]*c)
		a[c] += a[b]
		a[b] = 0

		fmt.Println(sum)
	}
	// fmt.Println(a)
}


func binarySearch(a []int, l, r int, key int) int {
	left := l
	right := r
	mid := 0

	for left < right {
		mid = (left + right) / 2
		if key == a[mid]{
			return mid
		}
		if key > a[mid] {
			left = mid + 1
		} else if key < a[mid] {
			right = mid
		}
	}
	return -1
}

type BufScanner struct {
	*bufio.Scanner
}

func NewBufScanner(r io.Reader) *BufScanner {
	s := bufio.NewScanner(r)
	s.Split(bufio.ScanWords)
	// s.Split(scanWords)
	return &BufScanner{s}
}

func scanWords(data []byte, atEOF bool) (advance int, token []byte, err error) {
	start := 0
	for isSpace(data[start]) {
		start++
	}
	for i := start; i < len(data); i++ {
		if isSpace(data[i]) {
			return i+1, data[start:i], nil
		}
	}
	if atEOF && len(data) > start {
		return len(data), data[start:], nil
	}
	return start, nil, nil
}
func isSpace(b byte) bool {
	return b == ' ' || b == '\n' || b == '\r' || b == '\t'
}

func (s *BufScanner) String() string {
	s.Scan()
	return s.Text()
}

func (s *BufScanner) Int() int {
	return int(s.UInt())
}

func (s *BufScanner) UInt() uint64 {
	s.Scan()
	i, e := strconv.ParseUint(s.Text(), 10, 64)
	if e != nil {
		panic(e)
	}
	return i
}

func lower_bound(arr []int, value int) int {
	l, r := 0, len(arr)
	for l < r {
		mid := (l + r) / 2
		if arr[mid] < value {
			l = mid + 1
		} else {
			r = mid
		}
	}
	return l
}


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

int main()
{
  ll A, B;
  cin >> A >> B;
  int i = 1;
  int count = 0;
  while (i < B)
  {
    i += (A - 1);
    count++;
  }
  cout << count << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));
//priority_queue<int,vector<int>, greater<int> > q2;



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

	int W, H;
	char c;
	char ans[30][30];
	cin >> W >> H >> c;
	REP(i, H) {
		REP(j, W) {
			if (j == 0 || j == W - 1) {
				if (i == 0 || i == H - 1) ans[i][j] = '+';
				else ans[i][j] = '|';
			}
			else {
				if (i == 0 || i == H - 1) ans[i][j] = '-';
				else ans[i][j] = '.';
			}
		}
	}
	ans[H / 2][W / 2] = c;
	REP(i, H) {
		REP(j, W) {
			cout << ans[i][j];
		}
		cout << endl;
	}
	return 0;
}




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

int main(){
    int h,w;
    cin>>h>>w;
    vector<vector<char>> c(h,vector<char>(w));
    vector<vector<char>> d(h,vector<char>(w));
    for(int i=0; i<h; i++) {
        for(int j=0; j<w; j++) {
            cin>>c[i][j];
            d[i][j]=c[i][j];
        }
    }
    for(int i=0; i<h; i++) {
        for(int j=0; j<w; j++) {
            cout<<c[i][j];
        }
        cout<<"\n";
        for(int j=0; j<w; j++) {
            cout<<d[i][j];
        }
      	cout<<"\n";
    }
}

Measured memory_bytes: 256
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

h,w = nm()
s = []
for y in range(h):
  s.append([_ for _ in input()])

for y in range(h):
  for x in range(w):
    xx = [1,0,-1,0]
    yy = [0,1,0,-1]

    if s[y][x]=='.':
      continue

    ok = False
    for i in range(4):
      nx = x + xx[i]
      ny = y + yy[i]

      if 0 <= nx < w and 0 <= ny < h:
        if s[ny][nx]=='#':
          ok = True
    if not ok:
      print('No')
      exit()
print('Yes')



Measured memory_bytes: 9228
# ALDS1_7_A: Rooted Trees

class Node
  attr_accessor :id, :parent, :left_child, :r_sib

  def initialize()
    @id = -1
  end

  def depth
    @parent.nil? ? 0 : 1 + @parent.depth
  end

  def parent_id
    @parent.nil? ? -1 : @parent.id
  end

  def child_ids
    child_ids = []
    child     = @left_child
    until child.nil?
      child_ids << child.id
      child = child.r_sib
    end
    child_ids
  end

  def type
    return 'root' if parent.nil?
    return 'leaf' if child_ids.empty?
    'internal node'
  end
end

n_nodes = gets.to_i
tree    = Array.new(n_nodes).map { Node.new }

n_nodes.times do
  id, n_child_ids, *child_ids = gets.split.map &:to_i
  tree[id].id = id
  next if child_ids.empty?

  leftmost = child_ids[0]
  tree[id].left_child = tree[leftmost]

  child_ids.each_with_index do |child_id, i|
    r_sib_id = child_ids[i + 1]
    tree[child_id].r_sib  = tree[r_sib_id] unless r_sib_id.nil?
    tree[child_id].parent = tree[id]
  end
end

tree.each do |n|
  puts "node #{n.id}: parent = #{n.parent_id}, " << 
  "depth = #{n.depth}, #{n.type}, #{n.child_ids}"
end

Measured memory_bytes: 29640
#include <stdio.h>

#define MAX_N 101
#define INF 100000000

int n, G[MAX_N][MAX_N], vis[MAX_N], size[MAX_N];

void dfs(int p, int t){
	vis[p] = t;
	for (int ix = 1; ix <= size[p]; ix++) 
		if ( t+1 < vis[G[p][ix]] ) 
			dfs(G[p][ix], t+1);
}

int main(){
	int u;
	scanf("%d", &n);
	for (int ix = 1 ; ix <= n; ix++){
		vis[ix] = INF;
		scanf("%d", &u);
		scanf("%d", &size[u]);
		for(int jx = 1; jx <= size[u]; jx++) 
			scanf("%d", &G[u][jx]);
	}
	dfs(1, 0);
	for (int ix = 1 ; ix <= n; ix++) 
		printf("%d %d\n",ix,(vis[ix] == INF) ? -1 : vis[ix]);
	return 0;
}


Measured memory_bytes: 2112
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(int i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(int i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(int i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define uniq(x) (x).erase(unique((x).begin(), (x).end()), (x).end())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    string s;
    cin >> s;
    map<char, int> d;
    
    rep(i, s.length()) {
        d[s[i]]++;
    }
    
    if (
        ((d['N'] > 0) != (d['S'] > 0)) ||
        ((d['W'] > 0) != (d['E'] > 0))
    ) {
        cout << "No" << endl;
    }
    else {
        cout << "Yes" << endl;
    }
    
    return 0;
}


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

const double PI=acos(-1.0);

double triangle_side(double a,double b,double angle)
{
    angle*=PI/180.0;
    double c=sqrt(a*a+b*b-2.0*a*b*cos(angle));
    return c;
}

double clock_angle(double m)
{
    double angle1=m/2.0;
    m=(int)m%60;
    double angle2=m*6.0;
    double angle=fabs(angle1-angle2);
    return angle;
}

int main()
{
    double a,b,h,m;
    cin>> a >> b >> h >> m;
    double angle=clock_angle(h*60.0+m);
    double side=triangle_side(a,b,angle);
    cout<< fixed <<setprecision(20)<< side <<endl;
    return 0;
}

Measured memory_bytes: 4224
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
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(){
    cin.tie(0);
    ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<set<int>> G(n);
	rep(i,m){
		int a, b;
		cin >> a >> b;
		a--; b--;
		G[a].insert(b);
		G[b].insert(a);
	}
	int ans = 0;
	vector<int> v(n);
	rep(i,n) v[i] = i;
	do{
		if(v[0] != 0) continue;
		bool yes = true;
		rep(i,n-1){
			if(G[v[i]].find(v[i+1]) == G[v[i]].end()) yes = false;
		}
		if(yes) ans++;
	} while(next_permutation(v.begin(), v.end()));
	cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
typedef pair<int, int> P;
const int inf = 1 << 21;
const ll INF = 1LL << 60;
const ll mod = 1e9+7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

// abc121d
ll f(ll a){
    if (a<=0) return 0;
    a++;
    ll ans = 0;
    rep(i, 50){
        ll loop = 1LL<<(i+1);
        ll cnt = (a/loop)*(loop/2);
        cnt += max(0LL, (a%loop)-(loop/2));\
        if (cnt%2){
            ans += (1LL<<i);
        }
    }
    return ans;
}

int main(){
    ll a, b;
    cin >> a >> b;
    ll ans = f(b)^f(a-1);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		String s = sc.next();
		char before = 0;
		for(int i = 0 ; i < s.length() ; i++) {
			char hoge = s.charAt(i);
			if(before == hoge) {
				System.out.println("Bad");
				System.exit(0);
			}
			before = hoge;
		}
		System.out.println("Good");

		sc.close();

	}

}


Measured memory_bytes: 23764
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    if (b % a == 0) {
      System.out.println(a + b);
    } else {
      System.out.println(b - a);
    }
  }
}


Measured memory_bytes: 21972
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  vector<ll> a;
  ll n,allxor=0;
  cin>>n;
  for(int i=0;i<n;i++){
    ll num;
    cin>>num;
    a.push_back(num);
    allxor^=num;
  }
  for(int i=0;i<n;i++) a[i]&=(~allxor);
  ll rnk=0;
  for(int i=59;i>=0;i--){
    int id=rnk;
    for(;id<n;id++){
      if(((a[id]>>i)&1)==1) break;
    }
    if(id==n) continue;
    if(id>rnk) a[rnk]^=a[id];
    for(int j=rnk+1;j<n;j++) a[j]=min(a[j],a[j]^a[rnk]);
    rnk++;
  }
  ll ans=0;
  for(int i=0;i<n;i++) ans=max(ans,ans^a[i]);
  cout<<ans*2+allxor<<endl;
}


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

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

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;


//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
inline ll toLL(string s) {ll v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

const ll INF = 1e10;
ll dp[110][100100];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N,W;
    cin >> N >> W;
    VI w(N),v(N);
    rep(i,N){
        cin >> w[i] >> v[i];
    }
    rep(i,N+1)rep(j,100100) dp[i][j] = INF;
    dp[0][0] = 0;
    rep(i,N){
        rep(j,100100){
            if(dp[i][j] + w[i] <= W){
                dp[i+1][j+v[i]] = min(dp[i+1][j+v[i]],dp[i][j] + w[i]);
            }
            dp[i+1][j] = min(dp[i+1][j],dp[i][j]);

        }
    }
    // rep(i,N+1){
    //     rep(j,100){
    //         if(dp[i][j] == INF) cout << "- ";
    //         else cout << dp[i][j] << ' ';
    //     }
    //     cout << endl;
    // }
    for(int i = 100010; i >= 0; i--){
        if(dp[N][i] != INF){
            cout << i << endl;
            return 0;
        }
    }
    cout << 0 << endl;
    return 0;
}


Measured memory_bytes: 80128
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        // xの範囲
        long a = sc.nextLong();
        long b = sc.nextLong();
        // yの範囲
        long c = sc.nextLong();
        long d = sc.nextLong();

        long resultA = a * c;
        resultA = resultA < a * d ? a * d : resultA;
        long resultB = b * c;
        resultB = resultB < b * d ? b * d : resultB;
        if (resultA < resultB) {
            System.out.println(resultB);
        } else {
            System.out.println(resultA);
        }
    }
}


Measured memory_bytes: 35652
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue
import numpy as np

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

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


# ===CODE===


def main():
    n = ni()
    a = []
    b = []
    for _ in range(n):
        ai, bi = ns()
        a.append(ai)
        b.append(bi)

    a.sort()
    b.sort()

    if n % 2:
        ans = b[n // 2] - a[n // 2] + 1
    else:
        ans = b[n // 2] + b[n // 2 - 1] - (a[n // 2] + a[n // 2 - 1]) + 1
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 43376
# C
N, T = map(int, input().split())
tv = list(map(int, input().split()))

res = 0

for i in range(len(tv)-1):
    if tv[i+1] - tv[i] < T:
        res += tv[i+1] - tv[i]
    else:
        res += T
res += T

print(res)

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

int main() {
    string S;
    cin >> S;
    
    int N = S.length();

    for(int i=0; i<=N/2; i++){
        if(S[i]!=S[N-1-i]){
            cout << "No";
            return 0;
        }
    }
    for(int i=0; i<=N/4; i++){
        if(S[i]!=S[N/2-1-i] || S[N/2+1+i]!=S[N-1-i]){
            cout << "No";
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


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

int main(){
  string str;
  getline(cin, str);
  for(int i = 0; i < str.size(); i++){
    if((str.at(i) >= 'a' && str.at(i) <= 'z') || (str.at(i) >= 'A' && str.at(i) <= 'Z')){
      if(str.at(i) >= 'A' && str.at(i) <= 'Z'){
        str.at(i) = str.at(i) - ('A' - 'a');
      }
      else{
        str.at(i) = str.at(i) + ('A' - 'a');
      }
    }
    cout << str.at(i);
  }
  cout << endl;
}


Measured memory_bytes: 3160
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
  unsigned int N;
  std::cin >> N;

  std::vector<unsigned int> d_vec;
  for (size_t i = 0; i < N; ++i) {
    unsigned int d;
    std::cin >> d;
    d_vec.push_back(d);
  }

  std::sort(d_vec.begin(), d_vec.end(), std::less<unsigned int>());

  const unsigned int abc_max = d_vec.at(N / 2 - 1);
  const unsigned int arc_min = d_vec.at(N / 2);

  std::cout << arc_min - (abc_max + 1) + 1 << std::endl;

  return 0;
}


Measured memory_bytes: 892
require 'pp'
# IS_DEBUG = true
IS_DEBUG = false
def dputs str
	if(IS_DEBUG)
		puts str
	end
end
def dpp str
	if(IS_DEBUG)
		pp str
	end
end

N,M=gets.chomp.split(' ').map{|n| n.to_i}
clcnt = 0
ccnt = 0
case N%2 + M%2
when 2
	clcnt = N+M-1
	ccnt = 1
when 1
	clcnt = (N%2)*(M/2*2)+(M%2)*(N/2*2)
	ccnt = 0
end
h = {}
0.upto(N-1){
	gets.chomp.split('').each{|a|
		h[a].nil? ? h[a]=1 : h[a]+=1
	}
}
# p clcnt
# p ccnt
# p h
h.each{|k,c|
	if(c%2==1)
		if(ccnt == 0 || clcnt < c-1)
			puts "No"
			exit(0)
		end
		ccnt -= 1
		if(c%4==2)
			if(clcnt < 2)
				puts "No"
				exit(0)
			end
			clcnt -= 2
		end
	elsif(c%4==2)
		if(clcnt < 2)
			puts "No"
			exit(0)
		end
		clcnt -= 2
	end
}
puts "Yes"


Measured memory_bytes: 2556
import java.util.*;
  
class Main{
    public static void main(String[] args){
        double p1 = 0.0;
        double p2 = 0.0;
        double p3 = 0.0;
        double p4 = 0.0;
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] x = new int[n];
        int[] y = new int[n];
        for(int i=0; i<n; i++){
            x[i] = scan.nextInt();
        }
        for(int i=0; i<n; i++){
            y[i] = scan.nextInt();
        }
        for(int i=0; i<n; i++){
            p1 += (double)Math.abs(x[i] - y[i]);
            p2 += (double)Math.pow(Math.abs(x[i] - y[i]), 2);
            p3 += (double)Math.pow(Math.abs(x[i] - y[i]), 3);
            if(p4 < Math.abs(x[i] - y[i])){
                p4 = Math.abs(x[i] - y[i]);
            }
        }
        System.out.println(p1);
        System.out.println(Math.sqrt(p2));
        System.out.println(Math.cbrt(p3));
        System.out.println(p4);
    }
}


Measured memory_bytes: 26612
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
//repマクロ定義
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
//allマクロ定義
#define all(v) v.begin(),v.end()
using namespace std;

int main(){
  int k;
  cin >> k;
  int e[32]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};

  cout << e[k-1] << endl;
}

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

 


int main()
{
   long int x;
   cin>>x;
   long int y=100;
   long int year=0;
   while(y<x)
   {
      y=y+y/100;
      year++;
   }
   cout<<year<<endl;



}


































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































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

typedef unsigned long long int ull;
typedef long double ldb;
typedef long long int ll;

#define MOD1        1000000007
#define MOD2        998244353
#define PI          3.1415926535897932384626433832795
#define FILL(a, value) memset(a, value, sizeof(a))
#define BOOST       ios_base::sync_with_stdio(false); cin.tie(NULL)
#define what_is(x)  cerr << #x << " is " << x << endl;
#define ASSERT(left,operator,right) { if(!((left) operator (right))){ std::cerr << "ASSERT FAILED: " << #left << #operator << #right << " @ " << __FILE__ << " (" << __LINE__ << "). " << #left << "=" << (left) << "; " << #right << "=" << (right) << std::endl; } }

#define rep01(k,n)      for (ll i=k; i<n; i++)
#define rep02(k,n)      for (ll j=k; j<n; j++)
#define rep03(k,n)      for (ll k=k; k<n; k++)
#define rep11(k,n)      for (ll i=k; i<=n; i++)
#define rep12(k,n)      for (ll j=k; j<=n; j++)
#define rep13(k,n)      for (ll k=k; k<=n; k++)
#define repIT(c,it)     for(typeof(c.begin()) it = c.begin(); it != c.end(); ++it)
#define all(c)      c.begin(), c.end()

using namespace std;

const double pi = acos(-1.0);
const double epsilon = 1e-9;        // Add epsilon when casting double to int to avoid rounding pitfall issues, eg, 0.94*8178 in int
const int maxn = 1e6+10;


void solve()
{
    ll n, m, c;
    cin >> n >> m >> c;

    vector<ll> b(m);
    for(auto &i: b)
        cin >> i;

    int ans = 0;
    int a;
    for(int i = 0; i < n; i++)
    {
        ll sum = 0;
        for(int j = 0; j < m; j++)
        {
            cin >> a;
            sum += a*b[j];
        }
        if(sum > -c)
            ans++;
    }
    cout << ans << "\n";
}

int main()
{
   

    int t = 1;
    //cin >> t;
    while(t--)
        solve();

    cerr << "Time elapsed: " << clock() / (double)CLOCKS_PER_SEC << endl;
    return 0;
}

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

#define len length()
#define sz size()
#define rep(i, n) for(int i = 0; i < n; i++)
#define sort(v) sort(v.begin(), v.end())
#define veci(a, n) vector<int> a(n)
#define vecs(a, n) vector<string> a(n)
#define psb(a) push_back(a)
#define ppb pop_back()
#define sp(n) cout << setprecision(n) << fixed

int main(){
    int N;
    cin >> N;
    vector<pair<int, int> > a(N);
    int ans=0;
    rep(i, N){
        cin >> a.at(i).first >> a.at(i).second;
        ans += a.at(i).second - a.at(i).first + 1;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repe(i, n) for (int i = 0; i <= (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef long long ll;
const int INF = 1e9;
const ll mod = 1000000007;
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main() {
    int n;
    cin >> n;
    if (n == 1) {
        cout << "Hello World" << "\n";
    } else {
        int a,b;
        cin  >> a >> b;
        cout << a+b << "\n";
    }
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <vector>

int main() {
    int N;
    std::cin >> N;

    std::vector<std::string> S;
    std::vector<int> P;
    S.reserve(N);
    P.reserve(N);
    std::string s;
    int p;
    for (int i = 0; i < N; ++i) {
        std::cin >> s >> p;
        S.push_back(std::move(s));
        P.push_back(p);
    }

    std::map<std::string, std::vector<std::tuple<int, int>>> m;
    for (int i = 0; i < N; ++i) {
        m[S[i]].emplace_back(i + 1, P[i]);
    }

    for (auto& i : m) {
        auto& v = i.second;
        std::sort(
            v.begin(), v.end(),
            [](const auto& left, const auto& right) { return std::get<1>(left) > std::get<1>(right); }
        );
    }

    for (const auto& i : m) {
        const auto& v = i.second;
        for (auto x : v) {
            std::cout << std::get<0>(x) << std::endl;
        }
    }
}


Measured memory_bytes: 256
N,W = map(int,input().split())
w,v = [],[]
dp = [[10**10]*100100 for _ in range(101)]
dp[0][0] = 0
for i in range(N):
    wi,vi = map(int,input().split())
    w.append(wi)
    v.append(vi)
for i in range(N):
    for sum_v in range(100100):
        if(sum_v - v[i]) >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v],dp[i][sum_v-v[i]]+w[i])
        dp[i+1][sum_v] = min(dp[i+1][sum_v],dp[i][sum_v])
ans = 0
for i in range(100100):
    if dp[N][i] <= W:
        ans = i
print(ans)


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

using namespace std;

const int N = 1005;
const int maxn = 2e4 + 5;

struct Item {
    int w, s, v;
    bool operator < (const Item &rhs) const {
        return w + s > rhs.w + rhs.s;
    }
} a[N];

int n, w[N], s[N], v[N];
long long dp[N][maxn];

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i].w >> a[i].s >> a[i].v;
    sort(a + 1, a + n + 1);
    memset(dp, -0x3f, sizeof(dp)); dp[0][maxn - 1] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < maxn; j++) {
            if (dp[i][j] > -1e18) {
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
                if (j >= a[i + 1].w) dp[i + 1][min(a[i + 1].s, j - a[i + 1].w)] = max(dp[i + 1][min(a[i + 1].s, j - a[i + 1].w)], dp[i][j] + a[i + 1].v);
            }
        }
    }

    long long ans = 0;
    for (int i = 0; i < maxn; i++) ans = max(ans, dp[n][i]);
    cout << ans;
    return 0;
}


Measured memory_bytes: 157312
n = int(input())
a = list(map(int, input().split()))

zeroFlag = False
kosuu = 0
absMin = 10000000000
ans = 0
for i in range(n):
    if(a[i]<0):
        kosuu += 1
    elif(a[i]==0):
        zeroFlag = True
    if(abs(a[i])<absMin):
        absMin = abs(a[i])
    ans += abs(a[i])

if(zeroFlag):
    print(ans)
else:
    if(kosuu%2==0):
        print(ans)
    else:
        ans -= 2*absMin
        print(ans)

Measured memory_bytes: 14412
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
#define int long long
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr long long INFL = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;
using Graph = vector<vector<int>>;



signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    string s;
    cin>>s;
    int ans=0;
    string S="";
    rep(i,s.size()){
        if(s[i]=='B'&&s[i+1]=='C'){
            S=S+'D';
            i++;
        }else{
            S=S+s[i];
        }
    }
    int c=0;
    for(int i=S.size()-1;i>=0;i--){
        if(S[i]=='A') ans+=c;
        else if(S[i]=='D') c++;
        else c=0;
    }
    cout << ans << endl;



}


Measured memory_bytes: 1452
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define SORT(c) sort((c).begin(),(c).end())
#define MEMSET(v, h) memset((v), h, sizeof(v))
#define sqr(x) ((x) * (x))
#define bit(n) (1LL<<(n))
#define pcnt(x) __builtin_popcountll(x)
#define PB push_back
#define MP make_pair
#define endl "\n"
using Edge = pair<int,int>;
using Graph = vector<vector<Edge>>;
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; }
// 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;}

bool visit[60][60];
bool land[60][60];
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

int w,h; 

bool dfs(int a,int b) {
  if(!visit[a][b] && land[a][b]){
    visit[a][b] = true;
    FOR(i,0,7){
      if(a+dx[i]>=0 && a+dx[i]<=h-1 && b+dy[i]>=0 && b+dy[i]<=w-1 && !visit[a+dx[i]][b+dy[i]] && land[a+dx[i]][b+dy[i]]){
        dfs(a+dx[i],b+dy[i]);
      };
    }
    return true;
  }
  return false;
}

int main() {
  while(1){
    cin >> w >> h;
    if(w==0 && h==0) break;

    FOR(i,0,h-1){
      FOR(j,0,w-1){
        int c; cin >> c;
        visit[i][j] = false;
        land[i][j] = c;
      }
    }

    int ans = 0;

    FOR(i,0,h-1){
      FOR(j,0,w-1){
        int track = ans;
        ans += dfs(i,j);
        // if(track!=ans) cout << i << " " << j << endl;
      }
    }
    cout << ans << endl;
  }

  


}




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

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

    int res=0;
    for(int i=N-1; i>=0; i--){
        for(int j=i-1; j>=0; j--){
            auto Lupper = next(L.begin(), j);
            res += distance(upper_bound(L.begin(), Lupper, L[i]-L[j]), Lupper);
        }
    }
    cout<<res<<endl;

    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <numeric>
using namespace std;
typedef long long unsigned int ll;

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

int main() {
  int A, B;

  cin >> A >> B;

  cout << (A * B - A - B + 1) << endl;

  return 0;
}


Measured memory_bytes: 256
import Control.Monad
import Control.Applicative
import Data.List

solve :: [Int] -> String
solve ns =
    unwords . map show $ sort ns

main =      
    mapM_ putStrLn =<< map solve . takeInputs . lines <$> getContents
    where
    takeInputs :: [String] -> [[Int]]
    takeInputs = takeWhile (not . all (== 0)) . map (map read . words) 


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

const double pi  = 2 * acos(0.0);
const double eps = 1e-8;

#define REP(i,a,b) for(int i=(a); i<(b);++i)
#define rep(i,n) REP(i,0,n)
#define INF (1<<29)
#define INFLL (1LL<<62)

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

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

int main(void) {
  ios_base::sync_with_stdio(false); cin.tie(0);
  int N; cin >> N;
  vector<int> A(N);
  vector<ll> S(N);

  rep(i, N) cin >> A[i];

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

  ll s = 0;
  rep(i, N) {
    s += A[i];
    S[i] = s;
  }

  int d = -1;
  rep(i, N - 1) {
    if (S[i] * 2 < A[i+1])
      d = i;
  }

  cout << N - d - 1 << endl;
  return 0; 
}


Measured memory_bytes: 1408
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mod 1000000007
#define maxn 100005
using namespace std;
struct mat
{
    int a[5][5];
    mat(){ memset(a,0,sizeof(a)); }
};
mat operator * (mat A,mat B)
{
	mat C;
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			for(int k=0;k<3;k++)
				C.a[i][j]=1ll*(C.a[i][j]+1ll*A.a[i][k]*B.a[k][j])%mod;
	return C;
}
mat operator ^ (mat A,int k)
{
	mat ret;
    for(int i=0;i<3;i++) ret.a[i][i]=1;
    while(k)
    {
        if(k&1) ret=ret*A;
        A=A*A;
        k>>=1;
    }
    return ret;
}
//----------QAQ-----------
int n,m,x[maxn],f[3];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) scanf("%d",&x[i]);
	x[++m]=n;
	mat A,C,E,ans;
	ans.a[2][0]=1;
	A.a[0][0]=1,A.a[0][1]=2,A.a[0][2]=1;
	A.a[1][0]=0,A.a[1][1]=1,A.a[1][2]=1;
	A.a[2][0]=0,A.a[2][1]=0,A.a[2][2]=1;
	C.a[0][0]=2,C.a[0][1]=2,C.a[0][2]=1;
	C.a[1][0]=1,C.a[1][1]=1,C.a[1][2]=1;
	C.a[2][0]=1,C.a[2][1]=0,C.a[2][2]=1;
	f[0]=1;
	for(int i=1;i<=m;i++)
	{
		mat tmp=(C^(x[i]-x[i-1]-1))*A;
		int g[3];
		for(int i=0;i<3;i++)
		{
			g[i]=0;
			for(int j=0;j<3;j++) g[i]=(g[i]+1ll*f[j]*tmp.a[j][i]%mod)%mod;
		}
		for(int i=0;i<3;i++) f[i]=g[i];
	}
	printf("%d\n",f[2]);
}

Measured memory_bytes: 512
main(i){float a,b,c,d,e,f,g,h;while(~scanf("%f%f%f%f%f%f%f%f",&a,&b,&c,&d,&e,&f,&g,&h))printf(!(a>g||a>h||c<e||d<f)?"YES\n":"NO\n");exit(0);}

Measured memory_bytes: 612
#include <iostream>
#include <set>
#include <sstream>

using namespace std;

int main()
{
    string tmp;
    getline(cin, tmp);
    stringstream ss(tmp);

    int perimeter, n;
    ss >> perimeter;
    ss.ignore(1);
    ss >> n;

    getline(cin, tmp);
    ss.clear();
    ss.str(tmp);

    set<int> inp;
    for (int i = 0; i < n; i++)
    {
        int tmp;
        ss >> tmp;
        ss.ignore(1);
        inp.insert(tmp);
    }

    int max_diff = 0, start_point = -1, left = -1;
    for (int i = 0; i < perimeter; i++)
    {
        if (inp.find(i) != inp.end())
        {
            if (start_point == -1) {
                start_point = i;
            }

            if (left == -1) {
                left = i;
            }
            else {
                if ((i - left) > max_diff) {
                    max_diff = (i - left);
                }
                left = i;
            }
        }
    }

    int tm = (perimeter - left) + (start_point);
    if (tm > max_diff) {
        max_diff = tm;
    }
    cout << perimeter - max_diff << endl;
}

Measured memory_bytes: 12292
/********************************
*** ******** ********** *********
*** * ****** ********* * ********
*** ** ***** ******** *** *******
*** *** **** ******* ***** ******
*** **** *** ****** ******* *****
*** ***** ** ***** +++++++++ ****
*** ****** * **** *********** ***
*** *******  *** ************* **
*** ******** ** *************** *
**********_**********************
* |   /  / \  \     /    /\     *
* |  /  |   |  \   /    /  \    *
* | /   |   |   \ /    /    \   *
* |+\   |   |    |    /______\  *
* |  \  |   |    |   |        | *
* |   \  \_/     |   |        | *
********************************/
#include<bits/stdc++.h>
#define lli long long int
#define MOD 1000000007
#define KING 1000000002
#define queen 1000002
#define fi first
#define se second
#define se second
#define lsb(i) (i & -i)
#define Pi 3.141592653589793238
#define nl cout<<'\n'
#define TEST cout<<"TEST",nl
#define all(a) a.begin(), a.end()
#define remax(a, b) (a = ((a<b) ? b : a))
#define remin(a, b) (a = ((a<b) ? a : b))
#define pr pair<lli,lli>
#define pb push_back
#define eb emplace_back
#define precise(a) cout<<fixed<<setprecision(a)
#define mp make_pair
#define vi vector<lli>
#define vpi vector<pr> 
#define P pair<lli,pr>
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define NA(i,s,n) for(lli i=s;i<n;i++)
using namespace std;

lli power(lli x,lli y,lli p) { 
	lli res = 1;	 
	x = x % p; 
	while (y > 0) 
	{ 
		if (y & 1) 
			res = (res*x) % p; 
		y = y>>1; 
		x = (x*x) % p; 
	} 
	return res; 
} 


const lli N = 5e5 + 6, M = 5e5 + 4;
lli bit[N] = {0}, a[M], last[N] = {0}, n, q, b, c;
vpi qs[M];

void update(lli pos, lli val){
    for(; pos<N; pos+=lsb(pos)) bit[pos] += val; 
    return;
}

lli query1(lli pos){
    lli res = 0;
    for(; pos>0; pos-=lsb(pos)) res += bit[pos];
    return res;
}

lli query(lli x, lli y){
    lli res = (query1(y) - query1(x-1));
    return res;
}

void solve(){
    cin >> n >> q;
    NA(i,1,n+1){
        cin >> a[i];
    } 
    vi res(q);
    NA(i,0,q){
        cin >> b >> c;
        qs[c].pb({b, i});
    }
    NA(i,1,n+1){
        if(last[a[i]]) update(last[a[i]], -1);
        update(i, 1);
        last[a[i]] = i;
        for(pr j:qs[i]){
            res[j.se] = query(j.fi, i);
        }
    }
    for(lli r:res) cout << r << '\n';
    return;
}

int main(){
    // fastIO;
    lli t = 1;
    // cin>>t;
    NA(i,0,t){
        solve();
    }
    return 0;

}


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

int main()
{
  int n, m;
  cin >> n >> m;
  vector<int> s(m), c(m);
  for (int i = 0; i < m; i++)
  {
    cin >> s[i] >> c[i];
    //cout << s[i] - 1 << endl;
  }
  
  for (int i = 0; i < 1000; i++)
  {
    string S = to_string(i); //to_string 数値を文字列に変える
    if (S.size() != n)
      continue;
    bool ok = true;
    for (int j = 0; j < m; j++)
    {
      if (S[s[j] - 1] != c[j] + '0')/*S[0]は百の位！
        701が入ってきたらS[2](1) != 2だから内側のループを抜けて702でまた戻ってくる*/
      {
        ok = false;
        break;
      }
    }
    if (ok)
    {
      cout << i << endl;
      return 0; //大事
    }
  }
  cout << -1 << endl;
}

Measured memory_bytes: 256
INF = 99999999
n = gets.to_i

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

for i in 0..(n-1)
  dp[i+1] = [dp[i+1], dp[i]+1].min
  
  max6 = -1
  while i+6**(max6+1) <= n
    max6 += 1
  end
  for j in 1..max6
    dp[i+6**j] = [dp[i+6**j], dp[i]+1].min
  end
  
  max9 = -1
  while i+9**(max9+1) <= n
    max9 += 1
  end
  for j in 1..max9
    dp[i+9**j] = [dp[i+9**j], dp[i]+1].min
  end
end

puts dp[n]

Measured memory_bytes: 14904
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(10);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
constexpr int MOD=1000000007;
//constexpr int MOD=998244353;
#define INF (1<<30)
#define LINF (lint)(1LL<<56)
#define endl "\n"
#define rep(i,n) for(lint (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(lint (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
#define fi first
#define se second
typedef long long lint;
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
const int MAX_N=2e5+5;

int main(void){
    int H,W,K;
    cin >> H >> W >> K;
    char S[H][W];
    rep(i,H) cin >> S[i];
    int ans=0;
    rep(i,(1<<H)) rep(j,(1<<W)){
        char C[H][W];
        rep(k,H) rep(l,W) C[k][l]=S[k][l];
        rep(k,H) if((1<<k)&i) rep(l,W) C[k][l]='.';
        rep(k,W) if((1<<k)&j) rep(l,H) C[l][k]='.';
        int cnt=0;
        rep(k,H) rep(l,W) if(C[k][l]=='#') cnt++;
        if(cnt==K) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3644