akhauriyash/Code-Regression huggingface dataset:
import sys
from math import gcd

input = sys.stdin.readline


def lcm(a, b):
    return (a * b) // gcd(a, b)


def main():
    N = int(input())
    A = list(map(int, input().split()))

    ans = 1
    for a in A:
        ans = lcm(ans, a)

    print(ans)


if __name__ == "__main__":
    main()



Measured memory_bytes: 5664
#include<bits/stdc++.h>
 
#define ll long long 
#define mkp make_pair 
#define fi first 
#define se second
#define pb push_back 
#define pf push_front 
#define ppb pop_back 
#define ppf pop_front 

using namespace std ;
 
int z , o , ans ;
 
int main(){
 

	string s ;

	cin >> s ;

	if( s[2]==s[3] && s[4] == s[5] ){
		cout <<"Yes"<< endl;
	}
	else{
		cout << "No" << endl ;
	}
	
 
}

Measured memory_bytes: 256
N, K = map(int, input().split())
inputs = [int(i) for i in input().split()]

def gcd(a, b):
    while b:
	    a, b = b, a % b
    return a

tmp = inputs[0]
if K in inputs:
    print('POSSIBLE')
elif max(inputs) < K:
    print('IMPOSSIBLE')
else:
    if N == 1:
        if K == inputs[0]:
            print('POSSIBLE')
        else:
            print('IMPOSSIBLE')
    else:
        for i in range(1, N):
            tmp = gcd(tmp, inputs[i])
        if tmp == 1:
            print('POSSIBLE')
        else:
            if (max(inputs) - K) % tmp == 0:
                print('POSSIBLE')
            else:
                print('IMPOSSIBLE')


Measured memory_bytes: 14224
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

ll a[105];

int main(){
    int n; cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a+n);
    int ans = 0;
    for (int i = 0; i < n; i++){
        for (int j = i+1; j < n; j++){
            for (int k = j+1; k < n; k++){
                if (a[i]==a[j] || a[i]==a[k] || a[j]==a[k]) continue;
                if (a[i]+a[j] > a[k]) ans++;
            }
        }
    }
    cout << ans << endl;

    return 0;
}


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

#define LL long long

int main(){
	

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

	LL a,b,c,k;
	cin>>a>>b>>c>>k;

	if(k%2 == 0){
		cout<<(a-b)<<endl;
	}else{
		cout<<(b-a)<<endl;
	}
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		double S, a, b, theta;
		try (Scanner sc = new Scanner(System.in)) {
			a = sc.nextInt();
			b = sc.nextInt();
			theta = sc.nextInt();
			S = a * b * Math.sin(Math.toRadians(theta)) / 2;
			System.out.println(S);
			System.out.println(a + b + Math.sqrt(a * a + b * b - 2 * a * b * Math.cos(Math.toRadians(theta))));
			System.out.println(2 * S / a);
		}
	}
}



Measured memory_bytes: 26472
#include <iostream>
#include <algorithm>
#include <map>
#include <numeric>
#include <queue>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for (int i=0; i< (int)(n); i++)
typedef long long ll;
bool DEBUG = false;

int main() {
    // input
    int N, K;
    cin >> N >> K;
    vector<ll> V(N);
    rep(i, N) cin >> V[i];

    // input check
    int num_minus = 0;
    ll sum_plus = 0;
    rep(i, N) {
        if (V[i] < 0) num_minus++;
        else sum_plus += V[i];
    }
    // if K is large enough to check all
    if (K >= N + num_minus) {
        if (DEBUG) cout << "enough K. finishing...  ";
        cout << sum_plus << endl;
        return 0;
    }

    // 
    ll ans = 0;
    int num_plus = N - num_minus;
    rep(max_dump, min(K/2, num_minus) + 1){
        if (DEBUG) cout << "max_dump: " << max_dump << endl;
        int max_num_take = K - max_dump;
        rep(max_num_take_from_right, max_num_take + 1){
            // take from V
            int max_num_take_from_left = max_num_take - max_num_take_from_right;
            vector<ll> taken;
            // take from left
            bool start = false;
            for (int left=max_num_take_from_left - 1; left >=0; left--){
                if (V[left] > 0) start = true;
                if (V[left] <= 0 && !start) continue;
                taken.push_back(- V[left]);
                push_heap(taken.begin(), taken.end());
            }
            // do same for right
            start = false;
            for (int right=N-max_num_take_from_right; right < N; right++){
                if (V[right] > 0) start = true;
                if (V[right] <= 0 && !start) continue;
                taken.push_back(- V[right]);
                push_heap(taken.begin(), taken.end());
            }

            // dump as long as front is originally negative
            rep(dump, max_dump) {
                if (!taken.empty() && taken.front() > 0) {
                    pop_heap(taken.begin(), taken.end());
                    taken.pop_back();
                }
                else break;
            }

            // sum all ans take max
            ans = max(ans, - accumulate(taken.begin(), taken.end(), 0LL));
        }
    }
    cout << ans << endl;
}

// dump: 0~K/2  operation: 0~(K-dump)  combination: operation
// time: (dump * log(operation)) * combination * dump => 50 * log(100) * 100 * 50

Measured memory_bytes: 3636
// srt: 2017年02月28日 15時26分48秒
// 《别老母》  黄景仁
// 搴帷拜母河梁去，白发愁看泪眼枯。
// 惨惨柴门风雪夜，此时有子不如无。
// end: 2017年02月28日 15時55分06秒

#include<cstdio>
#include<cstring>
inline void read(int&r)
{
	register char c;r=0;
	do c=getchar();while(c<'0'||c>'9');
	do r=r*10+c-'0',c=getchar();while(c>='0'&&c<='9');
}

char s[500001];
int next[27][500002];
#define min(a,b) a<b?a:b

int main()
{
	scanf("%s",s);

	int i,k,c,n=strlen(s),inf=n+1;
	for(k=0;k<=26;k++)next[k][n]=next[k][inf]=inf;
	for(i=n-1;i>=0;i--)
	{
		c=s[i]-'a'+1;
		next[c][i]=i+1;
		for(k=c+1;k<=26;k++)
			next[k][i]=next[k-1][next[k-1][i]];
		next[0][i]=next[26][next[26][i]];
		if(c>1)next[1][i]=next[1][next[0][i]];
		for(k=2;k<c;k++)
			next[k][i]=min(next[k-1][next[k-1][i]],next[k][next[0][i]]);
	}
	for(k=1;1<<k<=n;k++)
		for(i=0;i<n;i++)
			next[k][i]=next[k-1][next[k-1][i]];
	c=k-1;

	int q,l,r;read(q);
	while(q--)
	{
		read(l),read(r),l--;
		for(k=c;k>=0;k--)
			if(next[k][l]<=r)
				l=next[k][l];
		puts(l==r?"Yes":"No");
	}
}

Measured memory_bytes: 53760
H, W = map(int, input().split())
A = [input() for _ in range(H)]
A = list(filter(lambda a: any(x == '#' for x in a), A)) 
A = list(filter(lambda a: any(x == '#' for x in a), zip(*A)))
for a in zip(*A):
    print(''.join(a))

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

int main(void) {
  int N;
  cin >> N;

  int max = 0;
  int ans;
  for (int i = 1; i <= N; i++) {
    int tmp = 0;
    int res = i;
    bool odd = false;
    while (true) {
      tmp++;
      if (res % 2 == 1) {
        odd = true;
      }

      if (odd) {
        break;
      }

      res /= 2;
    }

    if (max < tmp) {
      max = tmp;
      ans = i;
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
n=int(input())
s=list(input())
for i in range(n):
    s[i]=int(s[i])

def idx(l, x):
    return [i for i, _x in enumerate(l) if _x == x]

lst=[idx(s,j) for j in range(10)]
len_lst=[len(lst[i]) for i in range(10)]

ans=0
switch=0

for i in range(10):
    for j in range(10):
        for k in range(10):
            if len_lst[i]>=1:
                place_num1=lst[i][0]
                for l in lst[j]:
                    if l>place_num1:
                        place_num2=l
                        switch=1
                        break
                if switch==1:
                    switch=0
                    for m in lst[k]:
                        if m>place_num2:
                            ans+=1
                            break

print(ans)

Measured memory_bytes: 10444
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

//構造体の宣言
typedef struct node{
    int key;    //格納される数字
    struct node *next, *prev;   //前後の構造体を指すポインタ
}node;

node *nil;

//構造体の初期化
void init(){
    nil = (node *)malloc(sizeof(struct node));
    nil->next = nil;
    nil->prev = nil;
}

//要素の追加
void insert(int key){
    node *x;
    x = (node *)malloc(sizeof(struct node));
    x->key = key;
    x->next = nil->next;
    nil->next->prev = x;
    nil->next = x;
    x->prev = nil;
}

//要素の検索
node* list_search(int key){
    node *cur = nil->next;
    while((cur != nil) && (cur->key != key)){
        cur = cur->next;
    }
    return cur;
}

//要素の削除
void delete_node(node *t){
    if(t == nil) return;    //要素がなければreturn
    t->prev->next = t->next;
    t->next->prev = t->prev;
    free(t);
}

//先頭の要素の削除
void delete_first(){
    delete_node(nil->next);
}

//最後の要素の削除
void delete_last(){
    delete_node(nil->prev);
}

//要素を指定して削除
void delete(int key){
    delete_node(list_search(key));
}

//要素を表示
void print_list(){
    node *cur = nil->next;
    int isf = 1;
    while(1){
        if(cur == nil) break;
        if(isf == 0) printf(" ");
        printf("%d", cur->key);
        cur = cur->next;
        isf = 0;
    }
    printf("\n");
}

int main(){
    int key, n, i;
    char com[20];

    //構造体の初期化
    init();

    //命令数の入力
    scanf("%d", &n);
    
    for(i = 0; i < n; i++){
        scanf("%s%d", com, &key);
        //insertコマンドの検出
        if(com[0] == 'i'){
            insert(key);
        //deleteコマンドの検出
        }else if(com[0] == 'd'){
            //deleteFirst, deleteLastの検出
            if(strlen(com) > 6){
                if(com[6] == 'F') delete_first();
                else if(com[6] == 'L') delete_last();
            }else{
                delete(key);
            }
        }
    }

    //結果の表示
    print_list();
    return 0;
}


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

using namespace std;
typedef long long ll;

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) x.begin(),x.end() //sortなどの引数を省略したい
#define SIZE(x) ll(x.size()) //sizeをsize_tからllに直しておく
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB emplace_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素
#define Umap unordered_map
#define Uset unordered_set

int main(){
    string s;
    cin >> s;
    ll cnt1 = 0, cnt2 = 0, n = ll(s.length());
    REP(i, n) if((i % 2 == 0 && s[i] == '0') || (i % 2 == 1 && s[i] == '1')) cnt1++;
    REP(i, n) if((i % 2 == 0 && s[i] == '1') || (i % 2 == 1 && s[i] == '0')) cnt2++;
    cout << min(cnt1, cnt2);
    return 0;
}

Measured memory_bytes: 3660
# -*- coding: utf-8 -*-
"""
AtCoder A
"""

import math
import numpy as np

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

# S = str(input()) # str(input()) == input() -> 'abc'
# S = list(input()) # abc -> ['a','b','c']




def main():
    N, A, B, C, D = list(map(int,input().split()))
    S= str(input())
    # print(S[2:5])-> [2]~[4]
    if C>D:
        if '##' in S[A-1:C+1]:
            print("No")
        elif "..." in S[B-2:D+1]:
            print("Yes")
        else:
            print("No")
    else:
        if '##' in S[A-1:D]:
            print("No")
        else:
            print("Yes")
    # elif C>D and  ("..." in S[B-2:])
    # print(S[B-2:])
    
if __name__ == "__main__":
    main()

Measured memory_bytes: 21148
n = int(input())
A = list(map(int, input().split()))

dp = [1000] + [0] * (n-1)

for i in range(1, n):
    dp[i] = dp[i-1]
    for j in range(0, i):
        v = dp[j] // A[j]
        dp[i] = max(dp[i], (A[i]-A[j]) * v + dp[j])
print(dp[-1])


Measured memory_bytes: 9180
#include <bits/stdc++.h>
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = ((int)(n)-1); i >= 0; i--)
#define all(x) (x).begin(),(x).end()
 
using namespace std;
using ll = long long;
 
struct edge { int to, cost; };
 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> P;
 
const int INF = 1e9;
const double EPS = 1e-10;
const int MOD = 1e9+7;
const double PI = acos(-1.0);
 
const int mx4[] = {0,1,0,-1};
const int my4[] = {1,0,-1,0};
const int mx8[] = {0,1,1,1,0,-1,-1,-1};
const int my8[] = {1,1,0,-1,-1,-1,0,1};

int main(){
	int n;
	cin >> n;
	vi h(n);
	rep(i,n) cin >> h[i];

	int flag = 1;
	for(int i = 1; i < n; i++){
		if(h[i] > h[i-1]) h[i]--;
		if(h[i]-h[i-1] < 0) flag = 0;
	}

	cout << (flag ? "Yes" : "No") << endl;

	return 0;
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {

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

    int res = 0;

    for (int i = 0; i < s.length() / 2; ++i) {
      if (s.charAt(i) != s.charAt(s.length() - i - 1))
        ++res;
    }

    System.out.println(res);
  }
}

Measured memory_bytes: 24788
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }
#define dump(x) cerr<<#x<<": "<<x<<endl;
#define bit(k) (1LL<<(k))
#define Yes "Yes"
#define No "No"
#define YES "YES"
#define NO "NO"
typedef long long ll;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;

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 int INF = (ll)1e9;
const ll INFLL = (ll)1e18+1;
const ll MOD = (ll)1e9+7;
const double PI = acos(-1.0);
/*
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const string dir = "DRUL";
*/

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    ll N,K;
    cin >> N >> K;
    vector<ll> A(N);
    rep(i,N){
        cin>>A[i];
        A[i]--;
        A[i] %= K;
    }
    vec<ll> cum(N+1, 0);
    rep(i,N){
        cum[i+1] = cum[i] + A[i];
        cum[i+1] %= K;
    }
    //cerr<<"    ";print(A);print(cum);
    map<ll, int> mp;
    ll ans = 0;
    rep(i,N+1){
        if(i >= K){
            mp[cum[i - K]]--;
        }
        ans += mp[cum[i]];
        mp[cum[i]]++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 15872
import sys
sys.setrecursionlimit(10**6)


def root(x):
    if c[x] == x:
        return x
    else:
        c[x] = root(c[x])
        return c[x]


def uni(x,y):
    rx = root(x)
    ry = root(y)
    c[ry] = rx


n, m = map(int, input().split())
c = [i for i in range(n)]
for i in range(m):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    uni(x,y)

for i in range(n):
    root(i)

print(len(set(c)))


Measured memory_bytes: 13200
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin>>N;
  vector<int>A(N);
  for(int i=0;i<N;i++){
    cin>>A.at(i);
    A.at(i)++;
  }
  vector<int>B(1000001);
  for(int i=0;i<N;i++){
    B.at(A.at(i)-1)++;
    B.at(A.at(i))++;
    B.at(A.at(i)+1)++;
  }
  sort(B.begin(),B.end());
  reverse(B.begin(),B.end());
  cout<<B.at(0)<<endl;
}
    

Measured memory_bytes: 4608
#include <iostream>

int main(int argc, char **argv)
{

    int H1,M1,H2,M2,K;

    std::cin >> H1 >> M1 >> H2 >> M2 >> K;

    int m0 = H1 * 60 + M1;
    int m1 = H2 * 60 + M2;

    int diff = m1 - m0 - K;

    std::cout << diff << std::endl;
    
}


Measured memory_bytes: 3632
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef unsigned long long int ulli;
typedef long double ld;
#define vec(s) vector

#define vvec(s) vector<vector
>
typedef vector<lli> vi;
typedef vector<vi> vvi;
typedef pair<lli,lli> pii;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Yes(x) cout<<(x?"Yes":"No")<<endl;
#define YES(x) cout<<(x?"YES":"NO")<<endl;
#define out(s) cout<<s<<endl;
#define pb(s) push_back(s);
#define sp " " 
#define INF 10000000000
#define LINF 9000000000000000000
#define all(s) s.begin(),s.end()
void vout(vi v){
    for(lli i=0;i<v.size();i++)
    cout<<v.at(i)<<endl;
}
int main(){
    cout << std::fixed << std::setprecision(10);
    string s;
    cin>>s;
    rep(i,3){
        if(s[i]==s[i+1]){ 
            out("Bad");
            return 0;
        }
    }
    out("Good");
}

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

vector <array<int, 10>> v;
array<int, 10> test;

int dfs(int A[10], int a, int n, int N,int m) {
    //cout << "test" << n << " " << N << " " << m << endl;
    if(n >= N) {
        //cout << "return" << A[0] << A[1] << A[2] << A[3] << A[4] << A[5] << A[6] << A[7] << A[8] << A[9] << endl;

        //vector <int[10]> tmp{ A[0] };
        for(int i = 0; i < 10; i++) {
            test[i] = A[i];
        }
        v.push_back(test);
        return true;
    } else {
        for(int i = a; i <= m; i++) {
            A[n] = i;
            //
            dfs(A, i, n+1, N, m);
        }
        return true;
    }
    //return false;
} 

int main() {
    int N, m, q;
    cin >> N >> m >> q;

    int a[51], b[51], c[51], d[51];
    for(int i = 1; i <= q; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        //cout << q << endl;
    }

    for(int i = 1; i <= m; i++) {
        int A[10];
        A[0] = i; 
        dfs(A, i, 1, N, m);
        //cout << i << "endb" << endl;
    }

    long long max = 0;
    for(int i = 0; i < (int)v.size(); i++) {
        int sum = 0;
        for(int j = 1; j <= q; j++) {
            int ta = a[j];
            int tb = b[j];
            
            if(v[i][tb-1] - v[i][ta-1] == c[j]) {
                //cout << i << " " << ta << tb << " " << c[j] << v[i][0] << v[i][1] << v[i][2] << endl;
                sum += d[j];
            }
        }
        
        if(sum > max) {
            max = sum;
            
        }

    }

    cout << max << endl;
}

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

using namespace std;

int check(int x)
{
  if (x==1) return 3e5; else
    if (x==2) return 2e5; else
      if(x==3) return 1e5; else return 0;
}

int main()
{
  int a,b;
  cin >> a >>  b;
  int ans=0;
  ans+=check(a);
  ans+=check(b);
  if (a==1 && b==1) ans+=4e5;
  cout << ans;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>

using namespace std;

const int N = 4e5 + 7;
const int INF = 1e9 + 239;

int dl[N];
int ei[N];
vector<pair<int, int>> g[N];

int used[N];

int res[N];
vector<int> dp[2][N];
vector<int> wr[2][N];
vector<int> sons[N];

void dfs(int cur) {
	used[cur] = 1;
	for (auto t : g[cur]) {
		if (!used[t.first]) {
			dfs(t.first);
			ei[t.first] = t.second;
			sons[cur].push_back(t.first);
		}
	}
	dp[0][cur].resize(sons[cur].size() + 1);
	dp[1][cur].resize(sons[cur].size() + 1);
	wr[0][cur].resize(sons[cur].size() + 1);
	wr[1][cur].resize(sons[cur].size() + 1);
	dp[dl[cur]][cur][0] = 1;
	for (int i = 0; i < (int)sons[cur].size(); i++) {
		for (int rv = 0; rv < 2; rv++) {
			for (int tk = 0; tk < 2; tk++) {
				int sv = tk;
				int son = sons[cur][i];
				if (!dp[sv][son].back()) continue;
				if (!dp[rv][cur][i]) continue;
				dp[rv ^ tk][cur][i + 1] = 1;
				wr[rv ^ tk][cur][i + 1] = tk;
			}
		}
	}
}

void rec(int cur, int rv) {
	for (int i = (int)sons[cur].size(); i > 0; i--) {
		int tk = wr[rv][cur][i];
		int son = sons[cur][i - 1];
		res[ei[son]] ^= tk;
		rv ^= tk;
		rec(son, tk);
	}
}

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

	int n, m;
	cin >> n >> m;
	vector<int> a(n);
	vector<int> b(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
	}
 	vector<int> sn = a;
	sn.push_back(0);
	sn.push_back(INF);
	sort(sn.begin(), sn.end());
	sn.resize(unique(sn.begin(), sn.end()) - sn.begin());
	for (auto &t : a) {
		t = lower_bound(sn.begin(), sn.end(), t) - sn.begin();
	}
	vector<int> ind(n);
	iota(ind.begin(), ind.end(), 0);
	sort(ind.begin(), ind.end(), [&](int i, int j) {
		return a[i] < a[j];
	});
	vector<int> nb(n);
	for (int i = 0; i < n; i++) {
		nb[i] = b[ind[i]];
	} 
	b = nb;
	b.insert(b.begin(), 0);
	b.push_back(0);
	
	n += 2;
	for (int i = 1; i < n; i++) {
		dl[i] = b[i] ^ b[i - 1];
	}
	for (int i = 0; i < m; i++) {
		int l, r;
		cin >> l >> r;
		l = lower_bound(sn.begin(), sn.end(), l) - sn.begin();
		r = prev(upper_bound(sn.begin(), sn.end(), r)) - sn.begin();
		if (l > r) continue;
		r++;
		g[l].push_back({r, i});
		g[r].push_back({l, i});
	}
	int ans = 1;
	for (int i = 0; i < n; i++) {
		if (!used[i]) {
			dfs(i);
			ans &= dp[0][i].back();
			if (!ans) {
				cout << -1 << endl;
				return 0;
			} else {
				rec(i, 0);
			}
		}
	}
	vector<int> tk;
	for (int i = 0; i < N; i++) {
		if (res[i]) {
			tk.push_back(i);
		}
	}
	cout << tk.size() << endl;
	for (auto t : tk) {
		cout << t + 1 << ' ';
	}
	cout << '\n';
}


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

using namespace std;


int extgcd(int a, int b, int& x, int& y) {
    int d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1;
        y = 0;
    }
    return d;
}

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

    int a, b, x, y;
    cin >> a >> b;
    extgcd(a, b, x, y);

    printf("%d %d\n", x, y);

    return 0;
}



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

int main()
{
	long long int n,sum=0;
	cin >> n;
	for(long long int i=1; i<=n; i++)
	{
		if(i%3!=0 && i%5!=0)
		sum+=i;
	}
	cout << sum;
	return 0;
}


Measured memory_bytes: 3636
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<vector>
#include<utility>
#include<stack>
#include<queue>
#include<list>
#include<bitset>
#include<functional>

#define FOR(i, a, b) for(long long int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for(long long int i=(a);i>=(b);i--)
#define MOD 1000000007
#define INF 1000000000 //2000000000
#define LLINF 1000000000000000000 //9000000000000000000
#define PI 3.14159265358979

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

int main(void) {
	char c[4][4];

	FOR(i, 1, 3) {
		cin >> c[i];
	}
	FOR(i, 1, 3) {
		cout << c[i][i - 1];
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N,K,L = list(map(int,input().split()))
Network1 = UnionFind(N)
Network2 = UnionFind(N)

for i in range(K):
    P,Q=list(map(int,input().split()))
    Network1.union(P-1, Q-1)

for i in range(L):
    R,S=list(map(int,input().split()))
    Network2.union(R-1, S-1)

D = {}
memo = [0]*N
for i in range(N):
    X=Network1.find(i)
    Y=Network2.find(i)
    memo[i] = str(X)+"_"+str(Y)
    D[str(X)+"_"+str(Y)] = D.get(str(X)+"_"+str(Y),0)+1
out = []
for i in range(N):
    out.append(D[memo[i]])
print(*out)


Measured memory_bytes: 153232
#include<bits/stdc++.h>
using namespace std;
#define INF = 2e9
#define LINF = 1e18
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()
#define dump(x) cout << #x << = << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO")
#define Yes(n) cout << ((n) ? "Yes" : "No")

int main(){

    int n, m;
    cin >> n >> m;

    vector<vector<int> > a(n, vector<int> (m));
    vector<int> b(m);

    rep(i, n){
        rep(j, m)cin >> a[i][j];
    }

    rep(i, m)cin >> b[i];

    rep(i, n){
        int out = 0;
        rep(j, m){
           out += a[i][j]*b[j];
        }
        cout << out << endl;
    }

}


Measured memory_bytes: 3176
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rrep(i,a,b) for(int i=(int)(a);i>=(int)(b);--i)
#define fore(i,a) for(auto &i:a)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define isin(i,a,b) ((a) <= (i) && (i) < (b))
#define uni(a) (a).erase(unique(all(a)),(a).end())
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)(a).size()
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
using ll  = long long;
using unit= unsigned;
using ull = unsigned long long;
using P   = pair<int,int>;
using vi  = vector<int>;
using vl  = vector<ll>;
using vvi = vector<vi>;
using vp  = vector<P>;
void _main(); int main(){ cin.tie(0); ios::sync_with_stdio(false); _main(); }
template<class T>void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T>void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T>void POSS(T condition){ if(condition) cout << "POSSIBLE" << endl; else cout << "IMPOSSIBLE" << endl; }
template<class T>void Poss(T condition){ if(condition) cout << "Possible" << endl; else cout << "Impossible" << endl; }
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; }
template<class T>T gcd(T a, T b){ if (b==0){ return a; }else{ return gcd(b, a%b); }}
template<class T>T lcm(T a, T b){ return a / gcd(a, b) * b; }
constexpr double eps = 1e-10;
constexpr int inf = INT_MAX / 2;
constexpr ll infl = 1LL << 60;

void _main() {
  int N, K;
  cin >> N >> K;
  int coin_cnt;

  double ans;
  if (N >= K) {
    ans = 1.0l * (N - K + 1) / N;
    coin_cnt = K - 1;
  } else {
    ans = 0.0;
    coin_cnt = N;
  }

  vi vec(coin_cnt);
  for (int i=coin_cnt, time=1, t=2; i>0; --i) {
    while (i*t < K) {
      ++time;
      t *= 2;
    }
    vec[coin_cnt-i] = time;
  }

  double t = 0.0;
  double coin=0.5;
  for (int i=0, cnt=1; i<coin_cnt; ++i) {
    while(vec[i] != cnt) {
      ++cnt;
      coin *= 0.5;
    }
    t += coin;
  }

  t /= N;
  ans += t;
  cout << setprecision(15) << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,...) for(int i = (a)*(strlen(#__VA_ARGS__)!=0);i<(int)(strlen(#__VA_ARGS__)?__VA_ARGS__:(a));++i)
#define per(i,a,...) for(int i = (strlen(#__VA_ARGS__)?__VA_ARGS__:(a))-1;i>=(int)(strlen(#__VA_ARGS__)?(a):0);--i)
#define foreach(i, n) for(auto &i:(n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define all(x) (x).begin(), (x).end()
#define bit(x) (1ll << (x))
#define lambda(RES_TYPE, ...) (function<RES_TYPE(__VA_ARGS__)>)[&](__VA_ARGS__) -> RES_TYPE
#define method(FUNC_NAME, RES_TYPE, ...) function<RES_TYPE(__VA_ARGS__)> FUNC_NAME = lambda(RES_TYPE, __VA_ARGS__)
using ll = long long;
//const ll MOD = (ll)1e9+7;
const ll MOD = 998244353;
const int INF = (ll)1e9+7;
const ll INFLL = (ll)1e18;
using namespace std;
template<class t>
using vvector = vector<vector<t>>;
template<class t>
using vvvector = vector<vector<vector<t>>>;
template<class t>
using priority_queuer = priority_queue<t, vector<t>, greater<t>>;
template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;}
template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;}
#ifdef DEBUG
#define debug(x) cout<<"LINE "<<__LINE__<<": "<<#x<<" = "<<x<<endl;
#else
#define debug(x) (void)0
#endif

namespace templates{
  ll modpow(ll x, ll b){
    ll res = 1;
    while(b){
      if(b&1)res = res * x % MOD;
      x = x * x % MOD;
      b>>=1;
    }
    return res;
  }

  ll modinv(ll x){
    return modpow(x, MOD-2);
  }

  bool was_output = false;
  template<class t>
  void output(t a){
    if(was_output)cout << " ";
    cout << a;
    was_output = true;
  }
  void outendl(){
    was_output = false;
    cout << endl;
  }
  ll in(){
    ll res;
    scanf("%lld", &res);
    return res;
  }

  template<class t>
  istream& operator>>(istream&is, vector<t>&x){
    for(auto &i:x)is >> i;
    return is;
  }

  template<class t, class u>
  istream& operator>>(istream&is, pair<t, u>&x){
    is >> x.first >> x.second;
    return is;
  }

  template<class t>
  void in(t&x){
    cin >> x;
  }

  template<class t>
  t in(){
    t res; cin >> res; return res;
  }

  template<class t>
  void out(t x){
    cout << x;
  }

  template<class t>
  vector<t> sorted(vector<t> line,function<bool(t,t)> comp=[](t a,t b){return a<b;}){
    sort(line.begin(),line.end(),comp);
    return line;
  }

  template<class t>
  vector<t> reversed(vector<t> line){
    reverse(line.begin(),line.end());
    return line;
  }
}

using namespace templates;

int main(){
  map<int,int> m;
  m[1] = 0;
  m[3] = 0;
  m[5] = 0;
  m[7] = 0;
  m[8] = 0;
  m[10] = 0;
  m[12] = 0;
  m[4] = 1;
  m[6] = 1;
  m[9] = 1;
  m[11] = 1;
  m[2] = 3;
  cout << (m[in()]==m[in()]?"Yes":"No") << endl;
  return 0;
}


Measured memory_bytes: 3612
#include<bits/stdc++.h>
//#include<iostream>
using namespace std;
//type
typedef long long ll;
#define pii pair<int, int>
#define vi vector<int>
//x * y * 1.0 can cause overflow
//constant
#define inf (int)(1e9+7)
#define mod (ll)(1e9+7)
#define INF (ll)(1e18)
#define eps 1e-10
//omission
#define eb emplace_back
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define all(v) v.begin(), v.end()
#define ios cin.tie(0); ios::sync_with_stdio(false)
#define FIX(a) cout << fixed << setprecision(a)
#define mp make_pair
//manip
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; }
#define UNIQUE(v) v.erase(unique(v.begin(), v.end(), v.end());
#define fill(x, y) memset(x, y, sizeof(x))
#define ceil(a, b) a / b + !!(a % b)
template<class T> T power_mod(T a, T b) {return b ? power(a * a % inf, b / 2) * (b % 2 ? a : 1) % inf : 1;}
template<class T> T power(T a, T b) {return b ? power(a * a, b / 2) * (b % 2 ? a : 1) : 1;}
#define LB(v, x) (int)(lower_bound(v.begin(), v.end(), x) - v.begin())
#define UB(v, x) (int)(upper_bound(v.begin(), v.end(), x) - v.begin())
template<typename T> T gcd(T a, T b) {if (b == 0) return a; return gcd(b, a % b);}
template<typename T> T lcm(T a, T b) {return a / gcd(max(a, b), min(a, b)) * b;} //先に割る!!
#define outa(a, n) rep(i, n) cout << a[i] << " "; cout << endl
#define out(a) cout << a << endl
#define outv(v) rep(i, SZ(v)) cout << v[i] << " "; cout << endl
#define ina(a, n) rep(i, n) cin >> a[i];
//loop
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep3(i, st, n) for (int i = st; i < n; ++i)
//algorithm
//double pointer, l start, how many adds, can be 0 -> init r = l, sum = 0
//bfs, not x, y, i, j
//not !(i % 2), i % 2 == 0
//minimal required terms
//cast caution
//look constraints always

int calc(int l, int r) {
    int ans = inf;
    rep3(i, l, r) {
        rep3(j, i + 1, r + 1) {
            chmin(ans, (i * j) % 2019);
        }
    }
    return ans;
}

random_device rnd;
mt19937 mt(rnd());
uniform_int_distribution<> rand100(2000, 3000);

int main() {
    
    int l, r;
    cin >> l >> r;
    if (l / 2019 + 1 < r / 2019) { //2019の倍数2つ以上ある
        cout << 0 << endl;
        return 0;
    }
    if (l <= 3 && r <= 673) {
        cout << 0 << endl;
        return 0;
    }
    
    l %= 2019; r %= 2019;
    while (r <= l) r += 2019;
    
    int ans = inf;
    int ll, rr;
    rep3(i, l, r) {
        rep3(j, i + 1, r + 1) {
            if (ans > (i * j) % 2019) {
                ans = (i * j) % 2019;
                ll = i; rr = j;
            }
        }
    }

    out(ans);
    //out(ll << " " << rr);
    //out(calc(l, r));
    //
    
    
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <map>

#define rep(i, N) for (int i = 0; i < (int)N; i++)
using namespace std;
typedef long long ll;
const ll LLINF = 9223372036854775807;
const int INF = pow(2,29);
const int MOD = 1000000007;

int main() {
  int N; cin >> N;
  int num = 0;
  while(N>=0) { num++; N-=num; }
  int omit = -1*N;
  for(int i=1; i<=num; i++) {
    if (i!=omit) cout << i << endl;
  }
  return 0;
}

Measured memory_bytes: 384
h,w=map(int,input().split())
pic=[["#" for i in range(w+2)]]
for i in range(h):
  s=list(input())
  s=["#"]+s+["#"]
  pic.append(s)
pic.append(["#" for i in range(w+2)])

for i in pic:
  print("".join(i))

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstdio>
using namespace std;


int main()
{
    char s[51][51];
    int h,w,i,j,cons,bns,k,l;
    bns=0;

    for(i=0; i<=50; i++)
    {
        for(j=i; j<=50; j++)
        {
            s[i][j]=s[j][i]='.';
        }
    }
    scanf("%d%d",&h,&w);
    getchar();
    bns++;

    if(bns!=1) printf("\n");
    for(i=1; i<=h; i++)
    {
        for(j=1; j<=w; j++)
        {
            scanf("%c",&s[i][j]);
        }
        getchar();
    }
    for(i=1; i<=h; i++)
    {
        for(j=1; j<=w; j++)
        {
            if(s[i][j]!='#')
            {
                cons=0;
                for(k=-1; k<=1; k++)
                {
                    for(l=-1; l<=1; l++)
                    {
                        if(s[i+k][j+l]=='#')
                            cons++;
                    }
                }
                s[i][j]='0'+cons;
            }
        }
    }


    for(i=1; i<=h; i++)
    {
        for(j=1; j<=w; j++)
        {
            printf("%c",s[i][j]);
        }
        printf("\n");
    }

    return 0;
}

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

int main() {
  int a, b;
  cin >> a >> b;
  int x = a * b;
  if (x % 2 == 0) {
    cout << "No" << endl;
  } else {
    cout << "Yes" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val(a, b, c, d) = readLine()!!.split(" ").map(String::toInt)

    val ans = when{
        a + b > c + d -> "Left"
        a + b < c + d -> "Right"
        else -> "Balanced"
    }

    println(ans)
}

Measured memory_bytes: 38028
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main{

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner scan =new Scanner(System.in);
		int X=scan.nextInt();
		int N=scan.nextInt();
		List<Integer> list = new ArrayList<>();
		 
		for(int i=0;i<N;i++) {
			int a=scan.nextInt();
			list.add(a);
		}
		
		for(int i=0;i<100;i++) {
			if(!list.contains(X-i)) {
				System.out.println(X-i);
				break;
			}else if(!list.contains(X+i)) {
				System.out.println(X+i);
				break;
			}
		}
	}

}


Measured memory_bytes: 35876
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.math.*;
 
public class Main {
	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(br.readLine());

		String[] str1 = br.readLine().split(" ");
		String[] str2 = br.readLine().split(" ");
		int[] t = new int [n]; 
		int[] a = new int [n]; 
		int max = 0;
		int maxnum = 0;
		for(int i = 0; i < n; i++){
			t[i] = Integer.parseInt(str1[i]);
			a[i] = Integer.parseInt(str2[i]);
			if(t[i]>max && t[i]==a[i]){
				max = t[i];
				maxnum = i;
			}
		}
		// 0 check
		for(int i = maxnum; i < n; i++){
			if(max<t[i]){
				sb.append('0');
				System.out.println(sb);
				return;
			}
		}
		for(int i = maxnum; i > -1; i--){
			if(max<a[i]){
				sb.append('0');
				System.out.println(sb);
				return;
			}
		}
		// count
		int[] p = new int [n];
		p[0] = 1;
		p[n-1] = 1;
		for(int i = 1; i < n; i++){
			if(t[i]>t[i-1]){
				p[i] = 1;
			}else{
				p[i] = t[i];
			}
		}
		for(int i = n-2; i > -1; i--){
			if(a[i]>a[i+1]){
				p[i] = 1;
			}else{
				if(p[i]>a[i])
					p[i] = a[i];
			}
		}
		p[0] = 1;
		p[n-1] = 1;
		long cnt = 1;
		final long mod = 1000000007;
		for(int i = 0; i < n; i++){
			cnt = (cnt*p[i])%mod;
		}
		sb.append(cnt);
		System.out.println(cnt);
	}
}

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

int main() {
  int K,A,B;
  bool OK = false;
  cin >> K >> A >> B;
  
  for(int i=A;i<=B;i++){
    if(i%K == 0){
      OK = true;
      break;
    }
  }
  
  if(OK)
    cout << "OK" << endl;
  else
    cout << "NG" << endl;
}


Measured memory_bytes: 3592
s = input()
a = int(s[:2])
b = int(s[2:])
if 1 <= a <= 12:
    if 1 <= b <= 12:
        print("AMBIGUOUS")
    else:
        print("MMYY")
elif 1 <= b <= 12:
    print("YYMM")
else:
    print("NA")


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

int main(){
    int n,num;
    int card[4][14];
    char mark;
    cin>>n;
    //initialize
    for(int i=0;i<4;i++){
        for(int j=0;j<14;j++){
            card[i][j]=0;
        }
    }
    for(int i=0;i<n;i++){
        cin>>mark>>num;
        switch (mark)
        {
        case 'S':
            card[0][num]=1;
            break;
        case 'H':
            card[1][num]=1;
            break;
        case 'C':
            card[2][num]=1;
            break;
        case 'D':
            card[3][num]=1;
            break;
        default:
            break;
        }
    }
    for(int i=0;i<4;i++){
        for(int j=1;j<14;j++){
            if(card[i][j]==0){
                switch (i)
                {
                case 0:
                    cout<<"S "<<j<<endl;
                    break;
                case 1:
                    cout<<"H "<<j<<endl;
                    break;
                case 2:
                    cout<<"C "<<j<<endl;
                    break;
                case 3:
                    cout<<"D "<<j<<endl;
                    break;
                default:
                    break;
                }
            }
        }
    }
    return 0;
}


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

int main()
{
	ll k , n;
	cin >> k >> n;

	ll arr[n], vec[n];

	for(int i = 0; i < n; i++)
	{
		cin >> arr[i];
		vec[i] = arr[i];
	}

	sort(vec, vec + n);

	// vector< ll >left;
	// vector< ll >right;

	 ll mid = k / 2, start_ind, end_ind;

	// for(int i = 0; i < n; i++)
	// {
	// 	if(vec[i] < mid)
	// 	{
	// 		left.push_back(vec[i]);
	// 	}
	// 	else if(vec[i] >= mid)
	// 	{
	// 		right.push_back(vec[i]);
	// 	}
	// }

	// int max_diff = 20 - abs(left[0] - right[right.size() - 1]);
	// int min_diff = abs(left[left.size() - 1] - right[0]);

	// if()

	ll max_diff;

	if(vec[n-1] - vec[0] >= mid)
	{
		max_diff =  k - (vec[n-1] - vec[0]);
		start_ind = n-1;
		end_ind = 0; 
	}
	else
	{
		max_diff = (vec[n-1] - vec[0]);
		start_ind = n-1;
		end_ind = 0;
	}

	for(int i = 0; i < n - 1; i++)
	{
		if(vec[i+1] - vec[i] >= max_diff)
		{
			max_diff = vec[i+1] - vec[i];
			start_ind = i;
			end_ind = i + 1;
		}
	}

	ll sum = 0;

	if(start_ind == n-1 && end_ind == 0)
	{
		for(int i = 0 ; i <=start_ind - 1; i++)
		{
			if(vec[i+1] - vec[i] > mid)
				sum += (k - (vec[i+1] - vec[i]));
			else
				sum += (vec[i+1] - vec[i]);
		}

	// for(int j = end_ind; j < n-1; j++)
	// {
	// 	if(vec[j+1] - vec[j] > mid)
	// 		sum += (k - (vec[j+1] - vec[j]));
	// 	else
	// 		sum += (vec[j+1] - vec[j]);
	// }
	}
	else 
	{
		for(int i = 0 ; i <=start_ind - 1; i++)
		{
			if(vec[i+1] - vec[i] > mid)
				sum += (k - (vec[i+1] - vec[i]));
			else
				sum += (vec[i+1] - vec[i]);
		}

		for(int j = end_ind; j < n-1; j++)
		{
			if(vec[j+1] - vec[j] > mid)
				sum += (k - (vec[j+1] - vec[j]));
			else
				sum += (vec[j+1] - vec[j]);
		}
		if(vec[n-1] - vec[0] > mid)
		{
			sum += (k - (vec[n-1] - vec[0]));
		}
		else
		{
			sum += (vec[n-1] - vec[0]);
		}
	}

	cout << sum << "\n";
}

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

typedef vector<unsigned int>vec;
typedef vector<vec> mat;

typedef tuple<ll, ll, ll> T;

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

const int MAX = 510000;

long long fac[MAX], finv[MAX], inv[MAX];

void comb_init() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

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

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;cin>>n;
  cout<<n*(n+1)/2<<endl;
}

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

struct dat {
	char n[13];
	double l;
	double h;
};

int main() {
	dat da[11]={{"light fly",0,48},{"fly",48,51},{"bantam",51,54},{"feather",54,57},{"light",57,60},{"light welter",60,64},
	{"welter",64,69},{"light middle",69,75},{"middle",75,81},{"light heavy",81,91},{"heavy",91,9999}};
 double k;
 while(cin >> k)  for (int i=0;i<11;i++) if (k>da[i].l && k<=da[i].h) cout << da[i].n << endl;
 return 0;
}

Measured memory_bytes: 1220
#include <iostream>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <map>

using namespace std;

int main(void) {
  int N;
  cin >> N;
  int B[N-1];
  for (int i = 0; i < N - 1; i++) {
    cin >> B[i];
  }
  if (N == 2) {
    cout << B[0] * 2 << endl;
    return 0;
  }
  int c = 0;
  for (int i = 0; i < N - 2; i++) {
    c += min(B[i], B[i+1]);
  }
  c += B[0] + B[N-2];
  cout << c << endl;
  return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
  
using namespace std;
  
typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P> PP;
  
static const double EPS = 1e-8;
  
static const int tx[] = {0,1,0,-1};
static const int ty[] = {-1,0,1,0};

int power[100001];

struct Node{
  int par;
  int diff;
  Node() : par(0),diff(0) {}
  Node(int p,int d) : par(p),diff(d) {}
};

class UnionFindTree {
private:
  Node* nodes;
public:
  UnionFindTree(int n){
    nodes = new Node[n]();
    for(int i=0;i<n;i++){
      nodes[i].par = i;
    }
  }

  ~UnionFindTree(){
    delete[] nodes;
  }

  Node find(int x){
    if(nodes[x].par == x){
      return nodes[x];
    } else {
      Node ret = find(nodes[x].par);
      return nodes[x] = Node(ret.par,ret.diff + nodes[x].diff);
    }
  }

  void unite(int x,int y,int up){
    Node rx = find(x);
    Node ry = find(y);
    if (rx.par == ry.par){
      return;
    }

    //rx.par == rx
    //ry.par == ry
    nodes[rx.par].par = ry.par;
    nodes[rx.par].diff = (power[y] - power[x] - up) + (ry.diff - rx.diff);
    find(x); //update
  }

  int dist(int x,int y){
    Node rx = find(x);
    Node ry = find(y);
    if(rx.par != ry.par) return INF;
    return (ry.diff - rx.diff) + (power[y] - power[x]);
  }

  bool same(int x,int y){
    return find(x).par == find(y).par;
  }
};

int main(){
  int total_players;
  int total_queries;
  while(~scanf("%d %d",
               &total_players,
               &total_queries)){
    
    UnionFindTree uft(total_players+1);
    memset(power,0,sizeof(power));
    for(int query_i = 0; query_i <total_queries; query_i++){
      string command;
      cin >> command;
      if(command == "IN"){
        int players[2];
        int up;
        cin >> players[0] >> players[1] >> up;
        power[players[0]] += up;
        power[players[1]] += up;
        uft.unite(players[0],players[1],up);
      }
      else if(command == "COMPARE"){
        int players[2];
        cin >> players[0] >> players[1];
        if(!uft.same(players[0],players[1])){
          printf("WARNING\n");
        }
        else{
          printf("%d\n",uft.dist(players[0],players[1]));
        }
      }
    }
  }
}

Measured memory_bytes: 2324