akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
#define MAX 100000
#define INFTY (1 << 30)

class Edge {
	public:
	    int t, w;
	    Edge() {}
	    Edge(int a, int b) {
		    t = a;
		    w = b;
			 
		}
};

vector<Edge> G[MAX];
int n, d[MAX];
bool vis[MAX];
int cnt;

void bfs(int s) {
	for(int i = 0; i < n; i++) d[i] = INFTY;
	queue<int> Q;
	Q.push(s);
	d[s] = 0;
	int u;
	while(!Q.empty()) {
		u = Q.front();
		Q.pop();
		for(int i = 0; i < G[u].size(); i++) {
			Edge e = G[u][i];
			if(d[e.t] == INFTY) {
				d[e.t] = d[u] + e.w;
				Q.push(e.t);
			}
		}
	}
}

 
void solve() {
	bfs(0);
	int maxv = 0, tgt = 0;
	for(int i = 0; i < n; i++) {
		if(d[i] == INFTY) continue;
		if(maxv < d[i]) {
			maxv = d[i];
			tgt = i;
		}  
	}
	
	bfs(tgt);
	maxv = 0;
	for(int i = 0; i < n; i++) {
		if(d[i] == INFTY) continue;
		if(maxv < d[i]) {
			maxv = d[i];
		}
	}
	
	cout << maxv << endl;
}

main() {
	int s, t, w;
	cin >> n;
	
	for(int i = 0; i < n - 1; i++) {
		cin >> s >> t >> w;
		
		G[s].push_back(Edge(t, w));
		G[t].push_back(Edge(s, w)); 
	}
	
	solve();
}

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

vector<pair<int,int> > v;

int N;
int main () {
    cin >> N;
    for(int i=0; i<N; i++) {
        int x;
        cin >> x;
        v.push_back(make_pair(x,i));
    }
    sort(v.begin(),v.end());
    int cnt = 0;
    for(int i=0; i<N; i++) {
        pair<int,int> P = v[i];
        if ( P.second % 2 != i%2 ) cnt++;
    }
    cout << cnt / 2 << endl;
    return 0;
}


Measured memory_bytes: 1528
#include <bits/stdc++.h>
#define REP(i,n,N) for(int i=n;i<N;i++)
#define p(S) cout<<S<<endl
using namespace std;

bool mprime[200001]={false};

void matuPrime(){
	mprime[0] = mprime[1] = true;
	for(int i=2;i*i<=200000;i++){
		for(int j=2;j<=200000/i;j++){
			mprime[j*i]=true;
		}
	}
}

int main(){
	int N,P;
	matuPrime();
	while(cin>>N>>P&&N!=-1){
		int count=0;
		vector<int> vt,sum;
		for(int i=N+1;count<100;i++){
			if(!mprime[i]){
				count++;
				vt.push_back(i);
				for(unsigned int j=0;j<vt.size();j++){
					sum.push_back(i+vt[j]);
				}
			}
		}
		sort(sum.begin(),sum.end());
		p(sum[P-1]);
	}
	return 0;
}

Measured memory_bytes: 3404
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define rep(i,a,n) for(ll i=a;i<n;i++)
#define PI 3.141592653
int main()
{
	ll n;
	cin>>n;
	cout<<setprecision(12)<<(double)2*PI*n<<"\n";
	return 0;
}

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

int main(){
  int N = 0;
  vector<int> ans(2000000);
  cin >> N;
  
  for(int i = 0;i < N - 1; i++){
    int x = 0;
    cin >> x;
    x--;
    ans.at(x) += 1;
  }
  
  for(int i = 0;i < N; i++){
    cout << ans.at(i) << endl;
  }
  
}

Measured memory_bytes: 10996
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<queue>
#include<functional>
#include<map>
#include<set>
#include<cstring>
#include<string>
#include<stack>
#include<malloc.h>
using namespace std;
//#define int long long
typedef pair<int, int> pii;
typedef priority_queue<pii, vector<pii>, greater<pii> > RPQ;
#define mk make_pair
#define INF (1 << 30)
#define INFL (1ll << 60ll)
#define mod 1000000007

int M = 5;
int N;
bool dic[100000000];
int toi[100];

int tokey(string s){
    int key = 0;
    int n = (int)s.size();
    for(int i = 0; i < n; i++){
        key *= M;
        key += toi[s[i] - 'A'];
    }
    return key;
}

signed main(){
    cin >> N;
    toi['A' - 'A'] = 1;
    toi['C' - 'A'] = 2;
    toi['G' - 'A'] = 3;
    toi['T' - 'A'] = 4;
    for(int i = 0; i < N; i++){
        string s, t;
        cin >> s >> t;
        int key = tokey(t);
        if(s[0] == 'i'){
            dic[key] = true;
        }
        else {
            if(dic[key])printf("yes\n");
            else printf("no\n");
        }
    }

    return 0;
}

/*

*/


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

int N;
int H[22];

int main(){
	cin >> N;
	for (int i = 0; i < N; ++i) cin >> H[i];
	int count = 1;
	int norm = -1;
	for (int i = 1; i < N; ++i){
		for (int j = 0; j < i; ++j){
			norm = max(norm, H[j]);
		}
		if(H[i] >= norm) count++;
		norm = -1;
	}

	cout << count << endl;
}

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

vector<bool> seen;

void dfs(vector<vector<int>> &g, int v){
    seen.at(v) = true;
    for(auto next_v: g.at(v)){
        if(seen.at(next_v)) continue;
        dfs(g, next_v);
    }
    return;
}

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

    vector<int> a(m), b(m);
    for (int i=0; i<m; i++){
        cin >> a.at(i) >> b.at(i);
    }

    int count = 0;
    
    //iの橋がない場合
    for (int i=0; i<m; i++){ 

        vector<vector<int>> g(n);

        //グラフを作成
        for(int j=0; j<m; j++){
            if(i == j) continue;
            int ta = a.at(j);
            int tb = b.at(j);
            ta--; tb--;
            g.at(ta).push_back(tb);
            g.at(tb).push_back(ta);
        }

        seen.assign(n, false);

        //dfs探索
        dfs(g, 0);

        //連結か調べる
        for(int j=0; j<n; j++){
            if (seen.at(j) == false){
                count++;
                break;
            }
        }

    }

    cout << count << endl;

    return 0;
}


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

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> p(n);
  for (int& pi : p) {
    cin >> pi;
  }
  sort(p.begin(), p.end());
  int ret = 0;
  for (int i = 0; i < k; ++i) {
    ret += p[i];
  }
  cout << ret << endl;
  return 0;
}


Measured memory_bytes: 3624
package main

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

func main() {
	sc := NewScanner()
	N, _, X, Y := sc.NextInt(), sc.NextInt(), sc.NextInt(), sc.NextInt()

	x := sc.NextIntArray()
	y := sc.NextIntArray()

	sort.Ints(x)
	sort.Ints(y)

	check := func() bool {
		for i := X + 1; i <= Y; i++ {
			if x[N-1] < i && i <= y[0] {
				return true
			} else {
				continue
			}
		}
		return false
	}()

	if check {
		fmt.Println("No War")
	} else {
		fmt.Println("War")
	}

}

type Scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewScanner() *Scanner {
	rdr := bufio.NewReaderSize(os.Stdin, 1000)
	return &Scanner{r: rdr}
}
func (s *Scanner) Next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}
func (s *Scanner) NextLine() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)
	return string(s.buf[start:])
}
func (s *Scanner) NextInt() int {
	v, _ := strconv.Atoi(s.Next())
	return v
}
func (s *Scanner) NextInt64() int64 {
	v, _ := strconv.ParseInt(s.Next(), 10, 64)
	return v
}

func (s *Scanner) NextIntArray() []int {
	s.pre()
	start := s.p
	result := []int{}
	for ; s.p < len(s.buf)+1; s.p++ {
		if s.p == len(s.buf) || s.buf[s.p] == ' ' {
			v, _ := strconv.ParseInt(string(s.buf[start:s.p]), 10, 0)
			result = append(result, int(v))
			start = s.p + 1
		}
	}

	return result
}
func (s *Scanner) NextInt64Array() []int64 {
	s.pre()
	start := s.p
	result := []int64{}
	for ; s.p < len(s.buf)+1; s.p++ {
		if s.p == len(s.buf) || s.buf[s.p] == ' ' {
			v, _ := strconv.ParseInt(string(s.buf[start:s.p]), 10, 64)
			result = append(result, v)
			start = s.p + 1
		}
	}
	return result
}

func (s *Scanner) NextMap() map[int]bool {
	s.pre()
	start := s.p
	mp := map[int]bool{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			mp[v] = true
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	mp[v] = true

	return mp
}

func (s *Scanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}
func (s *Scanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}


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

// @author: pashka

int gcd(int a, int b) {
    while (b > 0) {
        int c = a % b;
        a = b; b = c;
    }
    return a;
}

int main() {
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    long s = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                s += gcd(gcd(i, j), k);
            }
        }
    }
    cout << s << "\n";

    return 0;
}

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

#define pb push_back
#define mp make_pair
#define inside sl<=l&&r<=sr
#define outside r<sl||sr<l
#define INF 1000000009
#define mod 1000000007
using namespace std;
typedef long long ll;
#define line pair<ll,ll>

ll n, c;
ll h[200005];
ll dp[200005];

deque<line> cht;

double kes(line a, line b){
	double ans = (double)(b.second - a.second)/(double)(a.first-b.first);
	//cout << "ans: " << ans << endl;
	return ans;
}

void chtupdate(line ekle){
	//cout << "update: " << ekle.first << ", " << ekle.second << endl;
	// soldan saga
	if (cht.size() < 2) cht.push_front(ekle);
	else {
		line last = cht.front();
		cht.pop_front();
		while (cht.size() > 0 && kes(last, cht.front()) <= kes(last, ekle)){
			//cout << "silindi: " << last.first << ", " << last.second << endl;
			last = cht.front();
			cht.pop_front();
		}
		cht.push_front(last);
		cht.push_front(ekle);
	}
}

ll chtquery(ll x){
	//cout << "query(" << x << ")" << endl;
	// sagdan sola
	if (cht.size() == 0) return 0;
	else if (cht.size() == 1) return cht.back().first*x + cht.back().second;
	else {
		line last = cht.back();
		cht.pop_back();
		//cout << "last: " << last.first << ", " << last.second <<endl;
		//cout << "cht.back(): " << cht.back().first << ", " << cht.back().second << endl;
		//cout << "x: " << x << endl;
		while (cht.size() > 0 && kes(last, cht.back()) >= x){
			//if (kes(last, cht.back()) == x) cout << "aha esit" << endl;
			//cout << "silindi: " << last.first << ", " << last.second << endl;
			last = cht.back();
			cht.pop_back();
			//cout << "last: " << last.first << ", " << last.second <<endl;
			//cout << "cht.back(): " << cht.back().first << ", " << cht.back().second << endl;
			//cout << "x: " << x << endl;
		}
		cht.push_back(last);
		//cout << "ans: " << cht.back().first*x + cht.back().second << endl;
		return cht.back().first*x + cht.back().second;
	}
}

int main(){
	//freopen("stl.gir", "r", stdin);
	
	cin >> n >> c;
	for (int i = 0; i < n; i++) cin >> h[i];
	
	dp[n-1] = 0;
	chtupdate(mp(-2*h[n-1], dp[n-1] + h[n-1]*h[n-1]));
	for (int i = n-2; i >= 0; i--){
		dp[i] = chtquery(h[i]) + h[i]*h[i] + c;
		chtupdate(mp(-2*h[i], dp[i] + h[i]*h[i]));
	}
	
	//for (int i = 0; i < n; i++) cout << dp[i] << " "; cout << endl;
	
	cout << dp[0] << endl;
	
}

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

#define FOR(i, m, n) for(int (i) = (m); (i) < (n); (i)++)
#define FORN(i, m, n) for(int (i) = (m); (i) <= (n); (i)++)
#define FORR(i, m, n) for(int (i) = (m); (i) >= (n); (i)--)
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define repr(i, n) FORR(i, n, 0)
#define repnr(i, n) FORR(i, n, 1)
#define co(n) cout << (n) << endl
#define cosp(n) cout << (n) << ' '
#define setp(n) cout << fixed << setprecision(n);
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> Vec;

const ll INF = 1e9+1;
const ll LINF = 1e18+1;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const double PI = acos(-1);
const double EPS = 1e-9;
const int MAX_T = 3000;

int dp[MAX_T] = {};

bool desc(const P &a, const P &b){
	if(a.sc == b.sc) return a.fs > b.fs;
	else return a.sc > b.sc;
}

int main(void){
	int n, t;
	cin >> n >> t;
	vector<P> dish(n);
	rep(i, n) cin >> dish[i].fs >> dish[i].sc;
	sort(all(dish), desc);

	int ans = 0, sum = 0;
	rep(i, n){
		if(dish[i].fs == 1) continue;
		if(sum > t) break;
		fill_n(dp, t, 0);
		rep(j, n){
			if(j == i) continue;
			int a = dish[j].fs, b = dish[j].sc;
			FORR(k, t-1, a){
				dp[k] = max(dp[k], dp[k-a]+b);
			}
		}
		ans = max(ans, dp[t-1]+dish[i].sc);
		sum += dish[i].fs;
	}

	co(ans);

	return 0;
}


Measured memory_bytes: 256
N,x=map(int,input().split())
a=list(map(int,input().split()))
ans=0
for i in range(N-1):
  if x<a[i]+a[i+1]:
    ans+=a[i]+a[i+1]-x
    if a[i]+a[i+1]-x<=a[i+1]:
      a[i+1]=x-a[i]
    else:
      a[i+1]=0
print(ans)

Measured memory_bytes: 14548
#include<cmath>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<deque>
#include<queue>
#include<algorithm>
#include<list>
#include<cstring>
#include <numeric>

#define ll long long
#define int long long
#define ld long double
#define endl "\n"
#define debugv(v) cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(p) cerr<<#p<<'='<<(p.first)<<" "<<p.second<<endl;
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
#define output(x)   cout << (x ? "YES" : "NO")<<endl;
const ll MOD = 1e9 + 7;
const int N = 1000000000000001;
const int demo = 10;
using namespace std;
const ll cfmod=998244353;
ll gcd(ll a, ll b)
{
    if (a == 0)
        return b;
    return gcd(b % a, a);
}
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
char button[4]={'L','R','U','D'};

// Ahhiya thi lakhvanu chalu thasse....


signed main() {
    FAST
    int q = 1;
    //cin>>q;
    while (q--) {
        int n;
        cin>>n;
        int arr[n];
        for(int i=0;i<n;i++){
            cin>>arr[i];
        }
        sort(arr,arr+n);
        int last=n-2;
        int ans=arr[n-1];
        for(int i=0;i<n-2;i++){
            if(i%2){
                ans+=arr[last];
                last--;
            }
            else{
                ans+=arr[last];
            }
        }
        cout<<ans;
    }
}

Measured memory_bytes: 4724
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
char ma[1005][1005];
queue<pair< pair<int,int>,int> >q;
int main()
{
    int h,w;
    scanf("%d%d",&h,&w);
    for(int i=1;i<=h;i++)
    {
        getchar();
        for(int j=1;j<=w;j++)
        {
            scanf("%c",&ma[i][j]);
            if(ma[i][j]=='#')
                q.push({{i,j},0});
        }
    }
    int ans=0;
    while(!q.empty())
    {
        int x=q.front().f.f;
        int y=q.front().f.s;
        int step=q.front().s;
        q.pop();
        if(ma[x][y-1]=='.')
        {
            ma[x][y-1]='#';
            q.push({{x,y-1},step+1});
            ans=max(step+1,ans);
        }
        if(ma[x][y+1]=='.')
        {
            ma[x][y+1]='#';
            q.push({{x,y+1},step+1});
            ans=max(ans,step+1);
        }
        if(ma[x-1][y]=='.')
        {
            ma[x-1][y]='#';
            q.push({{x-1,y},step+1});
            ans=max(ans,step+1);
        }
        if(ma[x+1][y]=='.')
        {
            ma[x+1][y]='#';
            q.push({{x+1,y},step+1});
            ans=max(ans,step+1);
        }
    }
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 13328
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// 端点を間違えないように気をつけること!
#define FOR(i, m, n) for (ll i = (ll)(m); i <= (ll)(n); i++)
#define RFOR(i, m, n) for (ll i = (ll)(m); i >= (ll)(n); i--)
// 割り算をするときは自作関数syou,amariを使うこと!
// 入力は変数を宣言した直後に入れること!

int main()
{
    ll N, K;
    cin >> N >> K;
    ll start;
    ll num_block = 0;
    vector<ll> num_conti;
    char now;
    ll now_num = 0;
    char s;
    FOR(i, 1, N)
    {
        cin >> s;
        if (i == 1)
        {
            now = s;
            if (now == '0')
            {
                start = 0;
            }
            else
            {
                start = 1;
            }
            now_num = 1;
            num_block++;
        }
        else
        {
            if (now != s)
            {
                num_conti.push_back(now_num);
                now = s;
                now_num = 1;
                num_block++;
            }
            else
            {
                now_num++;
            }
        }
    }
    num_conti.push_back(now_num);
    if (start == 0)
    {
        vector<ll> tmp;
        tmp.push_back(0);
        FOR(i, 0, num_conti.size() - 1)
        {
            tmp.push_back(num_conti[i]);
        }
        num_conti = tmp;
    }
    if (2 * K + 1 >= num_conti.size())
    {
        cout << N << endl;
        return 0;
    }
    num_conti.push_back(0);
    ll Max = 0;
    ll sum = 0;
    ll startpoint = 0;
    ll endpoint = 2 * K;
    FOR(i, 0, 2 * K)
    {
        sum += num_conti[i];
    }
    Max = max(Max, sum);
    while (endpoint < num_conti.size() - 2)
    {
        endpoint += 2;
        startpoint += 2;
        sum += num_conti[endpoint] + num_conti[endpoint - 1];
        sum -= num_conti[startpoint - 1] + num_conti[startpoint - 2];
        Max = max(Max, sum);
    }
    cout << Max << endl;
}

Measured memory_bytes: 2548
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
#
#
# @stop_watch
def solve(a, b, x):
    import math
    LOOP = 100
    water_max = a ** 2 * b
    area_x = x / a
    half_angle = math.degrees(math.acos(a / math.sqrt(a ** 2 + b ** 2)))
    ans = 0
    if x > water_max / 2:
        top = half_angle
        btm = 0
        for _ in range(LOOP):
            ans = (top + btm) / 2
            angle_a = 90 - ans
            angle_b = ans
            angle_c = 90
            side_a = a  # ★
            side_c = a / math.cos(math.radians(angle_b))
            side_b = side_c * math.sin(math.radians(angle_b))  # ★
            area = side_a * side_b / 2 + side_a * (b - side_b)
            if area >= area_x:
                btm = ans
            else:
                top = ans
    else:
        top = 90
        btm = half_angle
        for _ in range(LOOP):
            ans = (top + btm) / 2
            angle_a = 90 - ans
            angle_b = ans
            angle_c = 90
            side_b = b  # ★
            side_c = b / math.sin(math.radians(angle_b))
            side_a = side_c * math.cos(math.radians(angle_b))  # ★
            area = side_a * side_b / 2
            if area >= area_x:
                btm = ans
            else:
                top = ans

    print(ans)


if __name__ == '__main__':
    # S = input()
    # N = int(input())
    a, b, x = map(int, input().split())
    # As = [int(i) for i in input().split()]
    # Bs = [int(i) for i in input().split()]
    solve(a, b, x)


Measured memory_bytes: 9368
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define EPS (1e-9)
#define INF (1e17)
#define PI (acos(-1))
//const double PI = acos(-1);
//const double EPS = 1e-15;
//long long INF=(long long)1E17;
#define i_7 (long long)(1e9+7)
//#define i_7 998'244'353
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
long long po(long a, long b){
    if(b==0){
        return 1;
    }
    
    long long z = po(a,b/2);
    z = mod(z*z);
    if(b%2!=0){
        z = mod(a*z);
    }
    return z;
}
 
bool prime_(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=std::sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}
 
long long gcd_(long long a, long long b){
  if(a<b){
    std::swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd_(b,a%b);
  }
}
 
long long lcm_(long long x, long long y){
  return (x/gcd_(x,y))*y;
}
 
//using namespace std;
//using namespace boost::multiprecision;
//using namespace __gnu_pbds;

int main(){
  using namespace std;
  int n, m;
  cin>>n>>m;
  if(n % 2 == 1){
    int l = 2, r = n;
    int num = 0;
    while(r - l >= 0){
      if(num == m) break;
      cout << l << ' ' << r << endl;
      l++; r--; num++;
    }
  }else{
    int num = 0;
    int l = 1, r = n;
    bool update = false;
    while(r - l > 0){
      if(num == m) break;
      if(r - l > n/2){
        cout << l << ' ' << r << endl;
        l++; r--; num++;
      }else{
        if(!update){
          l++;
          update = true;
        }
        cout << l << ' ' << r << endl;
        l++; r--; num++;
      }
    }
  }       
  return 0;
}


Measured memory_bytes: 3672
#AGC030 A
'''
問題:
解毒剤入りの美味しくないクッキーがA枚ある
解毒剤入りの美味しいクッキーがB枚ある
毒入りの美味しいクッキーがC枚ある

毒入りのクッキーを食べるとお腹を壊す
お腹を壊した状態では毒入りのクッキーを食べることはできない
お腹を壊した状態で解毒剤入りのクッキーを食べるとお腹が治る

美味しいクッキーは最大で何枚食べられるか?

考察:
毒入りの美味しいクッキーはA+B+1枚まで食べることができる
'''

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

print(str(min(A+B+1, C)+B))

Measured memory_bytes: 2940
#include <iostream>
#include <vector>

using namespace std;

long long GCD(long long a,long long b){return b?GCD(b,a%b):a;}

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

  long long res=A[0];
  for(int i=0;i<N;i++){
    res=GCD(res,A[i]);
  }

  cout<<res<<endl;

  return 0;
}


Measured memory_bytes: 1024
using System.Collections.Generic;
using System;

public class hello
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine().Trim());
        var s = Console.ReadLine().Trim();
        var sL = s.Length;
        var ans = 0;
        for (int i = 0; i < n; i++)
        {
            var t = Console.ReadLine().Trim();
            var tL = t.Length;
            var slist = new List<int>();
            var a = 0;
            while (true)
            {
                var a0 = t.IndexOf(s[0], a);
                if (a0 >= 0) { slist.Add(a0); a = a0 + 1; }
                else break;
            }
            foreach (var start in slist)
            {
                var chkL = (tL - start) / (sL - 1);
                for (int j = 1; j <= chkL; j++)
                {
                    var str = "";
                    for (int k = 1; k <= sL; k++)
                    {
                        var chk = j * (k - 1) + start;
                        if (chk > tL - 1) goto next;
                        str += t.Substring(chk, 1);
                    }
                    if (str == s)
                    {
                        ans++;
                        goto nextloop;
                    }
                }
                next:;
            }
            nextloop:;
        }
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 9240
#include <bits/stdc++.h>
#define N 100010
#define INF 100000010
using namespace std;
int main(){
	long long n,k,i,j,l,a[N],qdh[N],pos[N],unpos[N],maxs=-INF,mins=INF,tem,tem2;
	cin>>n>>k;
	qdh[0]=0;
	a[0]=0;
	pos[0]=0;
	unpos[0]=0;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		if(a[i]>0)
		{
			pos[i]=pos[i-1]+a[i];
			unpos[i]=unpos[i-1];
		}
		else
		{
			unpos[i]=unpos[i-1]+a[i];
			pos[i]=pos[i-1];
		}
		qdh[i]=qdh[i-1]+a[i];
	}
	for(i=0;i+k<=n;i++)
	{
		tem=qdh[i+k]-qdh[i];
		tem2=pos[i+k]-pos[i-1];
		maxs=max(maxs,tem+pos[n]-tem2);
		tem2=unpos[i+k]-unpos[i-1];
		mins=min(mins,tem+unpos[n]-tem2);
	}
	cout<<max(maxs,qdh[n]-mins)<<endl;
	return 0;
}

Measured memory_bytes: 3328
N = int(input())
S = input()
RL, WL = [0 for _ in range(N+1)], [0 for _ in range(N+1)]

for i in range(N):
  RL[i+1] = RL[i] + (S[i] == 'R')
  WL[i+1] = WL[i] + (S[i] == 'W')
mcnt = int(1e13) + 13
for i in range(N, 0, -1):
  if S[i-1] == 'R':
    mcnt = min(mcnt, RL[N] - RL[i] + max(0, WL[i-1] - RL[N] + RL[i]))
if RL[N] == 0:
  mcnt = 0
print(mcnt)

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

int main() {
    int N;
    cin >> N;
    for(int i=1;i<=9;i++){
        for(int j=1;j<=9;j++){
            if(i*j==N){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" <<endl;
}

Measured memory_bytes: 3628
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int n,grundy[201][101],a,b,ans;
int dfs(int a,int b){
    if(grundy[a][b]!=-1){
        return grundy[a][b];
    }
    set<int> se;
    if(a>0)se.insert(dfs(a-1,b));
    if(b>0)se.insert(dfs(a+1,b-1));
    for(int i=1;i<=a&&i<=b;i++){
        se.insert(dfs(a,b-i));
    }
    int res=0;
    while(se.count(res)){
        res++;
    }
    return grundy[a][b]=res;
}
int main(void){
    cin>>n;
    for(int i=0;i<201;i++)for(int j=0;j<101;j++)grundy[i][j]=-1;
    grundy[0][0]=0;
    for(int i=0;i<n;i++){
        cin>>a>>b;
        ans^=dfs(a,b);
    }
    if(ans==0)cout<<1<<endl;
    else cout<<0<<endl;
}



Measured memory_bytes: 3216
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

int main() {
    int h, a;
    cin >> h >> a;
    cout << (h + a - 1) / a << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
int a[100050];
int max2(int n1,int n2){
    if(n1<n2)return n2;
    else return n1;
}
int main(){
    int n;
    cin>>n;
    vector<int> buf_odd(100050,0);
    vector<int> buf_even(100050,0);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(i%2==0)buf_even[a[i]]++;
        else buf_odd[a[i]]++;
    }
    int even_max=0;
    int even_second=0;
    int even_tmp;
    int odd_max=0;
    int odd_second=0;
    int odd_tmp;
    for(int i=1;i<100010;i++){
        if(even_max<=buf_even[i]){
            even_tmp=i;
            even_second=even_max;
            even_max=buf_even[i];
        }
        if(odd_max<=buf_odd[i]){
            odd_tmp=i;
            odd_second=odd_max;
            odd_max=buf_odd[i];
        }
        if(odd_second<=buf_odd[i] && buf_odd[i]<odd_max)odd_second=buf_odd[i];
        if(even_second<=buf_even[i] && buf_even[i]<even_max)even_second=buf_even[i];
    }
    int ans;
    if(even_tmp!=odd_tmp)ans=even_max+odd_max;
    else ans=max2(even_max+odd_second,odd_max+even_second);
    int ans2;
    ans2=n-ans;
    cout<<ans2<<endl;
    return 0;
}

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

int main(int argc, char const *argv[])
{
	int x; cin >> x;
	if (x == 7 or x == 5 or x == 3) printf("YES\n");
	else printf("NO\n");
	return 0;
}

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

int main() {
  int N; cin >> N;
  int s = 0;
  vector<int> a(N);
  for (int i = 0; i < N; ++i) {
    cin >> a[i];
    s += a[i];
  }
  int mean[] = {s / N, s / N + 1};
  int ans[2] = {};
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < N; ++j) {
      ans[i] += pow((a[j] - mean[i]), 2);
    }
  }
  cout << min(ans[0], ans[1]) << endl;
  return 0;
}


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

/*
N個のボールをK色の色で塗る場合の数の問題。
最初のボールはK色から選べる。あとのボールはK-1色から。
答えの桁数に注意
2^31-1以下なのが条件としてあるので8bite(32bit)のlongを使う
*/

int main() {
    int N, K;
    cin >> N >> K;
    long comb = 1;
    for (int i = 0; i < N; i++)
    {
        if (i == 0)
        {
            comb *= K;
        }
        else
        {
            comb *= K - 1;
        }
    }

    cout << comb << endl;
}

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

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

    if(n % 10 == 3) s = "bon";
    else if(n % 10 <= 1 || n % 10 == 6 || n % 10 == 8) s = "pon";
    else s = "hon";

    cout << s << endl;
    return 0;
}

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

int n, m, t, ans = 0, a, bf;

int main() {
  int i;
  cin >> n >> m >> t;
  for(i = 0; i < n; ++i) {
    cin >> a;
    if(i == 0)
      ans += a - m;
    else if((a - bf) > 2 * m)
      ans += (a - bf) - 2 * m;
    if(i == n - 1 && (t - a) > m) ans += (t - a) - m;
    bf = a;
  }
  cout << ans << endl;
}


Measured memory_bytes: 3092
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <map>

#define rep(i,x) for(int i = 0; i < x; i++)
#define rrep(i,x) for(int i = 1; i <= x; i++)
#define srep(i,s,t) for (int i = s; i < t; ++i)
using ll = long long;
using namespace std;
const int INF = 1001001001;
const ll LINF = 1002003004005006007;

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

struct mint {
    ll x; // typedef long long ll;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const {
        return pow(mod-2);
    }
    mint& operator/=(const mint a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const {
        mint res(*this);
        return res/=a;
    }
};

//x^n
mint pow(mint x, ll n){
    if (n == 0) return 1;
    x = pow(x, n / 2);
    x *= x;
    if (n % 2 == 1) x *= 2;
    return x;
}

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

ll LCM(ll a, ll b) {
    return a / GCD(a, b) * b;
}

map<ll, ll> prime_factorize(ll N){
    map<ll, ll> res;
    for (ll a = 2; a * a <= N; a++) {
        if (N % a != 0) continue;
        ll ex = 0; // 指数
        // 割れる限り割り続ける
        while (N % a == 0) {
            ex++;
            N /= a;
        }
        // その結果を push
        res.insert(pair<ll, ll>{a, ex});
    }
    // 最後に残った数について
    if (N != 1) res.insert({N, 1});
    return res;
}

int main(){
    int n; cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    map<ll, ll> lcm_list;
    rep(i, n){
        map<ll, ll> primes = prime_factorize(a[i]);
        for (auto prime : primes){
            auto itr = lcm_list.find(prime.first);
            if (itr != lcm_list.end()){
                lcm_list[prime.first] = max(prime.second, itr->second);
            }else{
                lcm_list[prime.first] = prime.second;
            }
        }
    }
    mint lcm = 1;
    for (auto prime : lcm_list){
        lcm *= pow(prime.first, prime.second);
    }
    mint ans = 0;
    rep(i, n){
        ans += lcm / a[i];
    }
    cout << ans.x << endl;
}


Measured memory_bytes: 896
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
const long long mod = 1e9+7;
//////////////////////////////////

long long f(long long x) {
  return x*x*x*x*x;
}

int main() {
  long long x; cin >> x;
  for(long long a=0; ; a++) {
    for(long long b=a-1; b>=-a; b--) {
      if (f(a) - f(b) == x) {
        cout << a << " " << b << endl;
        return 0;
      }
    }
  }

  return 0;
}

// EOF


Measured memory_bytes: 3636
mod = 1_000_000_007

n = gets.to_s.to_i

h = Hash.new{|h, k| h[k] = [0, 0] }
genten_iwashi = 0

$<.read.split.map(&:to_i).each_slice(2) do |(a,b)|

  if a == 0 && b == 0
    genten_iwashi += 1
  else
    f = a.zero? || a * b > 0
    r = ( f ? Rational(a,b) : -Rational(b,a) )
    h[r][ f ? 0 : 1 ] += 1
  end
end

ans = 1
h.values.each do |(a, b)|
  ans *= ( 2.pow(a,mod) + 2.pow(b, mod) - 1)
  ans %= mod
end

ans = ( ans - 1 + genten_iwashi ) % mod

puts ans

Measured memory_bytes: 72416
#include <iostream>
#include <string>
#include <vector>
#include <algorithm> // sort
#include <map> // pair
#include <queue>
#include<iomanip>
#include <cmath>
#include <set>
#include <unordered_set>

#define ABS(x) ((x)>0?(x):-(x))
#define MIN(x,y) ((x)>(y)?(y):(x))
#define MAX(x,y) ((x)<(y)?(y):(x))

#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))

#define INF 1000000000

using namespace std;
typedef long long ll;

ll newton(long long int a, long long int  b)
{
	if(a==b)
		return a;
	while(a != 0 && b != 0)
	{
		if(a > b)
		{
			b += a;
			a = b-a;
			b -= a;
		}
		b %= a;
	}
	return a;
}

struct UnionFind {
	vector<int> p;
	UnionFind(int N):p(N)
	{
		for(int i=0; i< N; i++)
		{
			p[i] = i;
		}
	}
	int root(int x)
	{
		if(p[x] == x)
			return x;
		return p[x] = root(p[x]);
	}
	void unite(int x, int y)
	{
		int rx = root(x);
		int ry = root(y);
		if(rx == ry) return;
		p[rx] = ry;
	}
	bool issame(int x, int y)
	{
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};

//大きな数に対する割り算をするとき、MODを指定することで掛け算の値に変換できる

ll div2mul_calc(ll a, ll b, ll m)
{
	if (b == 0) {
        return 1;
    } else if (b % 2 == 0) {
        ll d = div2mul_calc(a, b / 2, m);
        return (d * d) % m;
    } else {
        return (a * div2mul_calc(a, b - 1, m)) % m;
    }
}
ll div2mul(ll n, ll mod)
{
	return div2mul_calc(n, mod-2, mod);
}

ll twoRow(ll a, ll b, ll mod)
{
	ll ret = 1;
	for(ll i = 1 ;i <= a+b;++i)
	{
		ret *= i;
		ret %= mod;
	}
	for(ll i = 1 ;i <= a;++i)
	{
		ret *= div2mul(i,mod);
		ret %= mod;
	}
	for(ll i = 1 ;i <= b;++i)
	{
		ret *= div2mul(i,mod);
		ret %= mod;
	}
	return ret;
}

struct edge {
    int from; //出発点
    int to;   //到達点
    int cost; //移動コスト
};

vector< ll > divisor(ll n) {
  vector< ll > ret;
  for(ll i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(ret.begin(), ret.end());
  return (ret);
}
/*
小数の桁数を指定する
	cout << setprecision(8)<< mp[0]-mx << endl;
*/
	ll mp[40000][10] = {0};
	ll two[40000][100] = {0};
	ll ans[1000] = {0};

int main()
{
	ll i,j,k,a,b,ans=0;
	char c;
	ll N,M,T, X,Y;
	string S;
	cin >> N;
	queue<ll> q;
	map<ll, ll> mp;
	ll flag = (1<<20)-1;
	mp[0] = 1;
	q.push(0);
	for(i=0;i<N;++i)
	{
		ans = 0;
		cin >> a;
		b = q.size();
		//cout << i << endl;
		for(j=0;j<b;++j)
		{
			k = q.front();
			//cout << (k&flag) << " " << ((k>>20)&flag) << " " << ((k>>40)&flag) << endl;
			q.pop();
			if(mp[k] != 0)
			{
				mp[k] %= 1000000007;
				if((k&flag) == a)
				{
					if(mp[k+1] == 0)
						q.push(k+1);
					mp[k+1] += mp[k];
					ans += mp[k];
				}
				if(((k>>20)&flag) == a)
				{
					if(mp[k+(1<<20)] == 0)
						q.push(k+(1<<20));
					mp[k+(1<<20)] += mp[k];
					ans += mp[k];
				}
				if(((k>>40)&flag) == a)
				{
					if(mp[k+((ll)1<<40)] == 0)
						q.push(k+((ll)1<<40));
					mp[k+((ll)1<<40)] += mp[k];
					ans += mp[k];
				}
				mp[k] = 0;
			}
		}
	}
	cout << ans % 1000000007 << endl;
	return 0;
}




















Measured memory_bytes: 37760
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<iomanip>


using namespace std;
typedef long long ll;
typedef vector<ll> v;
typedef vector<vector<ll>> vv;


#define MOD 1000000007
#define INF 1001001001
#define MIN -1001001001
#define rep(i,k,N) for(int i=k;i<N;i++)
#define MP make_pair
#define MT make_tuple //tie,make_tuple は別物
#define PB push_back
#define PF push_front
#define all(x) (x).begin(),(x).end()


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


int main(){
    ll N;
    cin>>N;
    v L(N);
    rep(i,0,N)cin>>L[i];
    ll ans = 0;
    rep(i,0,N)rep(j,i+1,N)rep(k,j+1,N){
        bool ok = false;
        v a(3);
        a[0] = L[i];
        a[1] = L[j];
        a[2] = L[k];
        sort(all(a));
        if(a[0] + a[1] >a[2])ok=true;
        if(a[0] == a[1] || a[1] == a[2])ok = false;
        if(ok){
            ans++;
            //cout<<i<<j<<k<<endl;
        }
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 3572
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int N= 1e5+3;

int a[N],b[N],c[N];

int32_t main() {

    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);

    int n;
    cin>>n;
    for(int i=0;i<=n;i++)cin>>a[i];
    for(int i=0;i<n;i++)cin>>b[i];
    int ans = 0;
    for(int i=0;i<=n;i++){
        // cerr<<c[i]<<' '<<a[i]<<' '<<b[i]<<endl;
        if(a[i]>=c[i]) {
            ans+=c[i];
            a[i]-=c[i];
        }
        else {
            ans+=a[i];
            a[i] = 0;
        }
        if(a[i]<=b[i]) {
            c[i+1]+=b[i]-a[i];
            ans+=a[i];
        }
        else ans+=b[i];
    } 
    cout<<ans<<endl;

    return 0;
}

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


#define ll long long int
ll fact(ll n){ll res = 1;for (ll i = 2; i <= n; i++)res = res * i,res%=1000000007; 
    return res; } 
 

int main()
{
    ll n,m;
    cin>>n>>m;
    
    if(max(n,m)-min(n,m)>=2)
		cout<<0;
	else
	{
		if(n==m)
		{
		    ll x=fact(n);
		    ll ans=(x*x*2)%1000000007;
		    cout<<ans;
		}
		else
		{
		    cout<<(fact(n)*fact(m))%1000000007;
		}
	}
	return 0;
    // cout<<(fact(100000)*fact(100000)*2)%1000000007;
}

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

int main(){
  int a, b, c;
  cin >> a >> b >> c;
  
  int count = 3;
  
  if(a == b && a == c) count -= 2;
  else if(a == b) count--;
  else if(a == c) count--;
  else if(b == c) count--;
  
  cout << count << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define all(x) (x).begin(), (x).end()
#define Sort(x) sort((x).begin(), (x).end())
#define Reverse(x) reverse((x).begin(), (x).end())
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, m, n) for (int i = m; i < n; i++)
#define INF INT_MAX
#define fcout cout << fixed << setprecision(15) // 15桁まで表示
#define en '\n'
using str = string;
using ll = long long;
using ull = unsigned long long;
using ui = unsigned int;
using puu = pair<ui, ui>;
using P = pair<int, int>;
using vi = vector<int>;
int gcd(int a, int b) {
  return b ? gcd(b, a % b) : a;
};
int lcm(int a, int b) {
  return a / gcd(a, b) * b;
};
int floor(int a, int b) {
  return (a + b - 1) / b;
};
int month[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
template <class T> inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
};
template <class T> inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
};
const ll mod = 1000000007;
const double PI = acos(-1.0);
int dp[3001][3001];
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(20) << setiosflags(ios::fixed);

  str s, t = "";
  int w;
  cin >> s >> w;
  for (int i = 0; i < s.size(); i += w)
    t += s[i];
  cout << t << en;
}

Measured memory_bytes: 3644
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <functional>
#include <map>
#include <iomanip>
using namespace std;

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

inline void readInt2(int *a, int *b) {
  int c, p = 0; char s[20] = "";
  for(int i = 0; (c = getchar()) != '\n'; i++) {
    if (c == ' ') { *a = atoi(s); strcpy(s, ""); p = i+1; continue; }
    else s[i] = c;
  }
  *b = atoi(s+p);
}
 
inline void readInt3(int *a, int *b, int *c) {
  int d, p = 0; char s[20] = "";
  for(int i = 0; (d = getchar()) != '\n'; i++) {
    if(d == ' ') {
      if(p == 0) { *a = atoi(s); strcpy(s, ""); p = i+1; continue; }
      else {*b = atoi(s+p); strcpy(s, ""); p = i+1; continue; }
    } else s[i] = d;
  }
  *c = atoi(s+p);
}
// UnionFindTree
class UnionFind {
private:
    int size_;
    vector<int> par, rank;
public:
    UnionFind() : size_(0), par(vector<int>(0)), rank(vector<int>(0)) {}
    UnionFind(int size_) : size_(size_) {
        par.resize(size_), rank.resize(size_);
        rep(i,size_) par[i] = i, rank[i] = 0;
    }
    // 現在のsize_を返す
    int size() { return size_; }
    // 親を返す
    int root(int x) { return (par[x] == x) ? x : par[x] = root(par[x]); }
    // ２つの頂点を連結する
    void unite(int x, int y) {
        x = root(x), y = root(y);
        if (x == y) return;
        if (rank[x] < rank[y]) {
            par[x] = y;
        } else {
            par[y] = x;
            if (rank[x] == rank[y]) rank[x]++;
        }
    }
    // 親が同じかを判定する
    bool same(int x, int y) { return root(x) == root(y); }
};

int n, k, l, p, q;
map<pair<int, int>, int> mp;

int main(void) {
    readInt3(&n, &k, &l);
    static UnionFind uf1(n), uf2(n);
    rep(i,k) {
        readInt2(&p, &q);
        uf1.unite(p-1, q-1);
    }
    rep(i,l) {
        readInt2(&p, &q);
        uf2.unite(p-1, q-1);
    }
    rep(i,n) {
        pair<int, int> p = make_pair(uf1.root(i), uf2.root(i));
        mp[p]++;
    }
    rep(i,n-1) {
        pair<int, int> p = make_pair(uf1.root(i), uf2.root(i));
        printf("%d ", mp[p]);
    }
    pair<int, int> p = make_pair(uf1.root(n-1), uf2.root(n-1));
    printf("%d\n", mp[p]);
}


Measured memory_bytes: 15104
import           Control.Monad
import qualified Data.ByteString.Char8 as BS
import           Data.Maybe

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

data Trend = Inc | Dec | Neu

main = do
  n <- getInt
  (a:as) <- getIntList

  let solve [] _ _ res = res
      solve (x:xs) y Inc res | x >= y    = solve xs x Inc res
                             | otherwise = solve xs x Neu (res+1)
      solve (x:xs) y Dec res | x <= y    = solve xs x Dec res
                             | otherwise = solve xs x Neu (res+1)
      solve (x:xs) y Neu res | x == y    = solve xs x Neu res
                             | x > y     = solve xs x Inc res
                             | otherwise = solve xs x Dec res

  print $ solve as a Neu 1

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

using namespace std;

int count_flip(const string &s) {
  int flips = 0;
  char prev = s[0];
  for (size_t i = 1; i < s.size(); ++i) {
    if (prev != s[i])
      ++flips;
    prev = s[i];
  }
  return flips;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  string s;
  cin >> s;
  int cnt = count_flip(s);
  reverse(s.begin(), s.end());
  cnt = min(cnt, count_flip(s));
  cout << cnt << "\n";
}


Measured memory_bytes: 512
import java.util.Scanner;
import java.util.Arrays;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(true){
        int n = sc.nextInt();  //??????????????°
        if(n==0)break;
        int[] value = new int[n]; //?????°?????????
        for(int i =0;i<n;i++){
          value[i] = sc.nextInt();
        }
        Arrays.sort(value);  //??????????????????
        int score = 0;
        for(int i=1;i<n-1;i++){ //????°??????¨?????§????????????????????°??§???????????????
          score += value[i];
        }
        System.out.println(score / (n-2));
        } //end_of_while
    }
}

Measured memory_bytes: 28824
x = [int(i) for i in input().split()]

A = x[0]
B = x[1]
C = x[2]
D = x[3]

L = A + B
R = C + D

if L == R:
  print('Balanced')
  
elif L > R:
  print('Left')
  
else:
  print('Right')

Measured memory_bytes: 3064
N = int(input())

ans = 0

L = []
isok = True
for i in range(N):
    n = int(input())
    if n>i: isok = False
    L.append(n)

for i in range(N-1):
    if L[i+1] <= L[i]:
        ans += L[i+1]
    elif L[i+1] == L[i]+1:
        ans += 1
    elif L[i+1] > L[i]:
        isok=False
        break
    
if isok:
    print(ans)
else:
    print(-1)

Measured memory_bytes: 11048
#include <set>
#include <cstdio>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

inline int getInt(){ int s; scanf("%d", &s); return s; }

using namespace std;

int a[100000 + 3];
int b[100000 + 3];

int main(){
  int n = getInt();

  REP(i,n){
    int aa = getInt();
    int bb = getInt();

    a[aa]++; b[bb]++;
  }

  int ans = 0;
  int peo = 1;

  REP(i,100000 + 3){
    peo += a[i];
    if(i > 0) peo -= b[i - 1];

    if(peo >= i){
      ans = i - 1;
    }
  }

  printf("%d\n", ans);

  return 0;
}

Measured memory_bytes: 1496
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Main {

    public static long knapsack2(int N, int W, int[] w, int[] v) {
        long[] dp = new long[100001];
        Arrays.fill(dp, Long.MAX_VALUE / 2);

        dp[0] = 0;
        for(int i = 0; i < N; i++) {
            for(int j = dp.length - 1; j >= v[i]; j--) {
                dp[j] = Math.min(dp[j], dp[j - v[i]] + w[i]);
            }
        }
        
        for(int i = dp.length - 1; i >= 0; i--) {
            if(dp[i] <= W) {
                return i;
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int W = sc.nextInt();
        
        int[] w = new int[N];
        int[] v = new int[N]; 

        for(int i = 0; i < N; i++) {
            w[i] = sc.nextInt();
            v[i] = sc.nextInt();
        }

        System.out.println(knapsack2(N, W, w, v));
  }
}


Measured memory_bytes: 24148
import java.util.*;

public class Main {
  static int n;
  static int m;
  static int q;
  static int[] a;
  static int[] b;
  static int[] c;
  static int[] d;
  static int ans;
  static int[] t;
  static int k;
  static int l;
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    m = sc.nextInt();
    q = sc.nextInt();
    a = new int[q];
    b = new int[q];
    c = new int[q];
    d = new int[q];
    t = new int[n + m - 1];
    k = n;
    l = m - 1;
    for(int i = 0; i < q; i++) {
      a[i] = sc.nextInt() - 1;
      b[i] = sc.nextInt() - 1;
      c[i] = sc.nextInt();
      d[i] = sc.nextInt();
    }
    dfs(0);
    System.out.println(ans);
  }

  public static void dfs(int p) {
    if(p == (n + m - 1)) {
      int[] r = new int[n];
      int c1 = 0;
      int c2 = 0;
      for(int i = 0; i < (n + m - 1); i++) {
        if(t[i] == 1) {
          r[c1] = (c2 + 1);
          c1++;
        } else {
          c2++;
        }
      }
      int w = 0;
      for(int i = 0; i < q; i++) {
        if((r[b[i]] - r[a[i]]) == c[i]) w += d[i];
      }
      ans = Math.max(ans, w);
    } else {
      if(k > 0) {
        if(l > 0) {
          t[p] = 1;
          k--;
          dfs(p + 1);
          k++;
          t[p] = 2;
          l--;
          dfs(p + 1);
          l++;
        } else {
          t[p] = 1;
          k--;
          dfs(p + 1);
          k++;
        }
      } else {
        t[p] = 2;
        l--;
        dfs(p + 1);
        l++;
      }
    }
  }
}

Measured memory_bytes: 46176
#include <bits/stdc++.h>
#include <stdio.h>
#include <math.h>
using namespace std;
using vi = vector<int>;
using vll = vector<long long int>;
using vb = vector<bool>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<long long int>>;
using ll = long long int;

int main(){
    ll N, K; cin >> N >> K;
    vb ans(N+1, true);
    for(int i=0; i<K; i++){
        ll d; cin >> d;
        vll a(d);
        for(int j=0; j<d; j++){
            cin >> a[j];
        }
        for(auto x: a){
            ans[x] = false;
        }
    }
    ll c=0;
    for(int i=1; i<N+1; i++){
        if(ans[i] == true){c++;}
    }
    cout << c;
}

Measured memory_bytes: 3636